Leet刷题---以图判树

81 阅读 0 评论 54 点赞

我是靠谱客的博主清新御姐，这篇文章主要介绍Leet刷题---以图判树，现在分享给大家，希望可以做个参考。

题目要求：
给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

示例 1：

输入: n = 5, 边列表 edges = [[0,1], [0,2], [0,3], [1,4]]
输出: true
示例 2:

输入: n = 5, 边列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
输出: false

解题：

复制代码

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
bool IsRing;
int Find(int *parent, int node)
{
if (parent[node] != node) {
parent[node] = Find(parent, parent[node]);
}
return parent[node];
}
void Join(int *parent, int node1, int node2)
{
int X = Find(parent, node1);
int Y = Find(parent, node2);
if (X == Y) {
IsRing = true;
return;
}
if (X < Y) {
parent[Y] = X;
} else {
parent[X] = Y;
}
return;
}
bool validTree(int n, int** edges, int edgesSize, int* edgesColSize){
int *parent = (int *)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
IsRing = false;
for (int i = 0; i < edgesSize; i++) {
Join(parent, edges[i][0], edges[i][1]);
if (IsRing) {
return false;
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == Find(parent, i)) {
cnt++;
}
}
return cnt == 1;
}

变形题：—无向图中连通分量的数目
给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

示例 1:

输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]

复制代码

输出: 2
示例 2:

输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

复制代码

1
2
3
4
5
6
 0
4
|
|
1 --- 2 --- 3

输出: 1
注意:
你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0] 相同，所以它们不会同时在 edges 中出现。

复制代码

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
int Find(int *parent, int node)
{
if (parent[node] != node) {
parent[node] = Find(parent, parent[node]);
}
return parent[node];
}
void Join(int *parent, int node1, int node2)
{
int X = Find(parent, node1);
int Y = Find(parent, node2);
if (X < Y) {
parent[Y] = X;
} else {
parent[X] = Y;
}
return;
}
int countComponents(int n, int** edges, int edgesSize, int* edgesColSize){
int *parent = (int *)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (int i = 0; i < edgesSize; i++) {
Join(parent, edges[i][0], edges[i][1]);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == Find(parent, i)) {
cnt++;
}
}
return cnt;
}```