1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
// 2685. Count the Number of Complete Components
#include "leetcode.h"
/*
* you are given an integer 'n'. there is an undirected graph with 'n' vertices,
* numbered from 0 to 'n - 1'. you are given a 2d integer array 'edges' where
* 'edges[i] = [a_i, b_i]' denotes that there exists an undirected edge
* connecting vertices 'a_i' and 'b_i'. return the number of complete connected
* components of the graph. a connected component is a subgraph of a graph in
* which there exists a path between any two vertices and no vertex of the
* subgraph shares an edge with a vertex outside of the subgraph. a connected
* component is said to be complete if there exists an edge between every pair
* of its vertices
*/
int countCompleteComponents(int n, int **edges, int edgesSize,
int *edgesColSize) {
int *vertices = (int *)calloc(n, sizeof(int));
int *edge_cnt = (int *)calloc(n, sizeof(int));
int *vert_cnt = (int *)calloc(n, sizeof(int));
int group = 1, ans = 0;
for (int i = 0; i < edgesSize; i++) {
int v1 = edges[i][0];
int v2 = edges[i][1];
if (!(vertices[v1] + vertices[v2])) {
vertices[v1] = vertices[v2] = group;
edge_cnt[group] = 2;
vert_cnt[group++] = 1;
} else if (!vertices[v1]) {
vertices[v1] = vertices[v2];
++edge_cnt[vertices[v2]];
++vert_cnt[vertices[v2]];
} else if (!vertices[v2]) {
vertices[v2] = vertices[v1];
++edge_cnt[vertices[v1]];
++vert_cnt[vertices[v1]];
} else if (vertices[v1] == vertices[v2])
++vert_cnt[vertices[v1]];
else {
vert_cnt[vertices[v1]] += vert_cnt[vertices[v2]] + 1;
edge_cnt[vertices[v1]] += edge_cnt[vertices[v2]];
edge_cnt[vertices[v2]] = vert_cnt[vertices[v2]] = 0;
for (int i = 0; i < n; i++)
if (vertices[i] == vertices[v2])
vertices[i] = vertices[v1];
}
}
int connect_cnt = 0;
for (int i = 1; i < group; i++) {
int edges = edge_cnt[i], verts = vert_cnt[i];
if (edges && (edges * (edges - 1) / 2 == verts))
++ans;
connect_cnt += edges;
}
free(vert_cnt);
free(edge_cnt);
free(vertices);
return ans + (n - connect_cnt);
}
int main() {
int e1i[4][2] = {{0, 1}, {0, 2}, {1, 2}, {3, 4}},
e2i[5][2] = {{0, 1}, {0, 2}, {1, 2}, {3, 4}, {3, 5}};
struct two_d_arr e1, e2;
two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
printf("%d\n", countCompleteComponents(6, e1.arr, e1.row_size,
e1.col_size)); // expect: 3
printf("%d\n", countCompleteComponents(6, e2.arr, e2.row_size,
e2.col_size)); // expect: 1
two_d_arr_free(&e1);
two_d_arr_free(&e2);
}
|