3587. 连通图(吉林大学考研机试题)

思路：求连通性可用并查集或者dfs，bfs

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int p[N];
int n, m;

int find(int x){
    
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    
    while(cin >> n >> m){
    
        for(int i = 1; i <= n; i ++) p[i] = i;
        while(m --){
    
            int a, b;
            cin >> a >> b;
            p[find(a)] = find(b);
        }
        
        bool res = true;
        
        for(int i = 2; i <= n; i ++)
            if(find(i) != find(1)){
    
                res = false;
                break;
            }
            
        if(res) puts("YES");
        else puts("NO");
    }
    
    return 0;
}