题意:给定 n 条边,判断是不是树。
析:水题,判断是不是树,首先是有没有环,这个可以用并查集来判断,然后就是边数等于顶点数减1.
代码如下:
#include <bits/stdc++.h> using namespace std;
const int maxn =1000 + 5;
int p[maxn]; int Find(int x){ return x == p[x] ? x : p[x] = Find(p[x]); } int main(){
int n, m, x, y;
cin >> n >> m;
bool ok = true;
for(int i = 1; i <= n; ++i) p[i] = i;
for(int i = 0; i < m; ++i){
scanf("%d %d", &x, &y);
x = Find(x);
y = Find(y);
if(x == y) ok = false;
else p[y] = x;
} if(ok && m == n-1) puts("yes");
else puts("no");
return 0;
}