Check whether a set of edges really forms a spanning tree.
What to build
A program that decides if the given edges form a spanning tree of the n vertices.
Requirements
- Use union-find to detect an edge that would make a cycle.
- Print
yesonly if there aren - 1edges and none of them makes a cycle. - Print
nootherwise.
Input
The first line has n and m. Each of the next m lines has an edge u v.
Output
yes or no.
Constraints
1 ≤ n ≤ 100 and 0 ≤ m ≤ 1000, with u ≠ v.
Example
Input:
4 3
0 1
1 2
2 3
Output:
yes
Why it works
Each edge that joins two different groups cuts the number of groups by one. Starting from n groups, n − 1 such edges leave exactly one group and no cycle, which is a spanning tree.
Examples
Example 1 · Input
4 3 0 1 1 2 2 3
Expected output
yes
Example 2 · Input
4 3 0 1 1 2 0 2
Expected output
no
Hints
Hint 1
A spanning tree on `n` vertices has exactly `n - 1` edges.
Hint 2
Use union-find. If an edge joins two vertices already in the same group, it makes a cycle.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int parent[100];
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) parent[i] = i;
int ok = m == n - 1;
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
int a = find(u), b = find(v);
if (a == b) ok = 0;
else parent[a] = b;
}
printf("%s\n", ok ? "yes" : "no");
return 0;
}