/**
* @param {number} n
* @param {number[][]} edges
* @return {number}
*/
var countPairs = function(n, edges) {
const g = new Array(n).fill(null).map(() => []);
for (const [x, y] of edges) {
g[x].push(y);
g[y].push(x); // 建图
}
const vis = new Array(n).fill(false);
function dfs(x) {
vis[x] = true; // 避免重复访问同一个点
let size = 1;
for (let y of g[x]) {
if (!vis[y]) {
size += dfs(y);
}
}
return size;
}
let ans = 0, total = 0;
for (let i = 0; i < n; i++) {
if (!vis[i]) { // 未访问的点：说明找到了一个新的连通块
const size = dfs(i);
ans += size * total;
total += size;
}
}
return ans;
};
impl Solution {
pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>) -> i64 {
let n = n as usize;
let mut g = vec![vec![]; n];
for e in &edges {
let x = e[0] as usize;
let y = e[1] as usize;
g[x].push(y);
g[y].push(x); // 建图
}
fn dfs(x: usize, g: &Vec<Vec<usize>>, vis: &mut Vec<bool>) -> i32 {
vis[x] = true; // 避免重复访问同一个点
let mut size = 1;
for &y in &g[x] {
if !vis[y] {
size += dfs(y, g, vis);
}
}
size
}
let mut ans = 0i64;
let mut total = 0;
let mut vis = vec![false; n];
for i in 0..n {
if !vis[i] { // 未访问的点：说明找到了一个新的连通块
let size = dfs(i, &g, &mut vis);
ans += size as i64 * total as i64;
total += size;
}
}
ans
}
}
func countPairs(n int, edges [][]int) (ans int64) {
g := make([][]int, n)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
vis := make([]bool, n)
tot, size := 0, 0
var dfs func(int)
dfs = func(x int) {
vis[x] = true
size++
for _, y := range g[x] {
if !vis[y] {
dfs(y)
}
}
}
for i, b := range vis {
if !b {
size = 0
dfs(i)
ans += int64(size) * int64(tot)
tot += size
}
}
return
}
class Solution {
public:
long long countPairs(int n, vector<vector<int>> &edges) {
vector<vector<int>> g(n);
for (auto &e : edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x);
}
bool vis[n]; memset(vis, 0, sizeof(vis));
long ans = 0L;
int cnt = 0;
function<void(int)> dfs = [&](int x) {
vis[x] = true;
++cnt;
for (int y: g[x]) if (!vis[y]) dfs(y);
};
for (int i = 0, tot = 0; i < n; ++i)
if (!vis[i]) {
cnt = 0;
dfs(i);
ans += (long) cnt * tot;
tot += cnt;
}
return ans;
}
};
class Solution {
List<Integer>[] g;
boolean[] vis;
int cnt;
public long countPairs(int n, int[][] edges) {
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x);
}
vis = new boolean[n];
var ans = 0L;
for (int i = 0, tot = 0; i < n; ++i)
if (!vis[i]) {
cnt = 0;
dfs(i);
ans += (long) cnt * tot;
tot += cnt;
}
return ans;
}
void dfs(int x) {
vis[x] = true;
++cnt;
for (var y : g[x]) if (!vis[y]) dfs(y);
}
}
class Solution:
# bfs
def countPairs(self, n: int, edges: List[List[int]]) -> int:
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)
visited = [False for _ in range(n)]
cc = 0
cc2nodes = defaultdict(set)
for i in range(n):
if not visited[i]:
cc += 1
que = deque()
que.append(i)
while que:
u = que.popleft()
if u not in cc2nodes[cc]:
cc2nodes[cc].add(u)
for v in graph[u]:
if not visited[v]:
visited[v] = True
que.append(v)
cnts = map(len, cc2nodes.values())
res = 0
for cnt in cnts:
res += cnt * (n - cnt)
return res // 2
'''
dfs 求连通块的大小
建图后，用 DFS 可以求出每个连通块的大小。
求连通块的大小的同时，用一个变量 tot 维护前面求出的连通块的大小之和。
设当前连通块的大小为 size，那么它对答案的贡献就是 size⋅tot。
累加所有贡献，即为答案。
'''
class Solution:
def countPairs(self, n: int, edges: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
vis, ans, tot, size = [False] * n, 0, 0, 0
def dfs(x: int) -> None:
nonlocal size
vis[x] = True
size += 1
for y in g[x]:
if not vis[y]:
dfs(y)
for i in range(n):
if not vis[i]:
size = 0
dfs(i)
ans += size * tot
tot += size
return ans
