题解 | #连通图#

#include <iostream>

using namespace std;
//给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

int father[1001];
int height[1001];//这个是解决超时的关键点吗？表这棵树的高度.增加这个快一毫秒
bool setCount = true;

void InitSet(int n) {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
        height[i] = 0;
    }
}

int FindFather(int u) {
    if (u == father[u]) {
        return u;
    } else {
        return FindFather(father[u]);
    }
}

void UnionSet(int u, int v) {
    int u_root = FindFather(u);
    int v_root = FindFather(v);
    if (height[u_root] < height[v_root]) {//v_root的高度更高，是根节点。
        father[u_root] = v_root;
    } else if (height[u_root] > height[v_root]) {
        father[v_root] = u_root;
    } else {
        father[v_root] = u_root;
        height[u_root]++;
    }
//    father[v_root] = u_root;
//    height[u_root]++;
}

int main() {
    int n;//顶点数目
    int m;//图中边的数目
//    vector<int> vertax(1001);//0表示未出现过
    while (scanf("%d%d", &n, &m) != EOF) {
        if (0 == n) {
            break;
        }
        setCount = true;
        InitSet(n + 1);
        //输入
        for (int i = 0; i < m; ++i) {
            int a;
            int b;
            scanf("%d%d", &a, &b);
            UnionSet(a, b);
        }
        int root = FindFather(1);
        for (int i = 1; i <= n; ++i) {
            if (FindFather(i) != root) {
                setCount = false;
                break;
            }
        }
        if (!setCount) {
            printf("NO\n");
        } else {
            printf("YES\n");
        }

    }

    return 0;
}