题解 | 连通图

#include<iostream>
using namespace std;

const int MAX = 100;

void Initial(int S[], int length) {
    for (int i = 0; i < length; i++) {
        S[i] = -1;
    }
}

// 优化FInd
int Find(int S[], int x) {
    int root = x;
    while (S[root] >= 0) {
        root = S[root];
    }

    int temp = S[x];
    while (S[x] >= 0) {
        S[x] = root;
        x = temp;
        temp = S[x];
    }

    return root;
}

// 优化Union
void Union(int S[], int x, int y) {
    int Root1 = Find(S, x);
    int Root2 = Find(S, y);

    if (Root1 == Root2) {
        return;
    }

    if (S[Root1] < S[Root2]) {
        S[Root1] += S[Root2];
        S[Root2] = Root1;
    } else {
        S[Root2] += S[Root1];
        S[Root1] = Root2;
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) {
            break;
        }
        int* S = (int*)malloc(sizeof(int) * (n + 1)); // S[0]不使用
        Initial(S, n + 1);

        int x, y;
        for (int i = 0; i < m; i++) {
            cin >> x >> y;
            Union(S, x, y);
        }

        // 判断并查集中是否只有一个集合
        int count = 0;
        for (int i = 1; i < n + 1; i++) {
            if (S[i] < 0) {
                count++;
            }
        }

        if (count > 1) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    }
}

通过并查集判断无向图的连通问题