并查集

这道题需要判断所给出的集合能否构成树,因此不仅需要判断所有节点属于一个集合,还需要判断各个节点是否符合树的定义。

而判断各个节点是否符合树的定义可以转换为判断它的入度是否符合要求,根节点的入度为0,其余节点的入度为1。只要各个节点满足入度要求,只有一个根节点,以及各个节点都属于同一个集合,就可以构成一颗树。

#include <iostream>
#include <vector>
using namespace std;

const int maxN = 10000;
vector<int> inDegree(maxN, 0);
vector<int> s(maxN, -1);
vector<bool> visited(maxN, false);

void Initial() {
    for (int i = 1; i < maxN; i++) {
        s[i] = -1;
        inDegree[i] = 0;
        visited[i] = false;
    }
}
 
int Find(vector<int>& s, int x) {
    int root = x;
    while (s[root] >= 0) {
        root = s[root];
    }
    while (x != root) {
        int t = s[x];
        s[x] = root;
        x = t;
    }
    return root;
}
 
void Union(vector<int>& s, int a, int b) {
    int roota = Find(s, a);
    int rootb = Find(s, b);
    if (roota == rootb) return;
    if (s[roota] <= s[rootb]) {
        s[roota] += s[rootb];
        s[rootb] = roota;
    }
    else {
        s[rootb] += s[roota];
        s[roota] = rootb;
    }
}

bool IsTree() {
    int component = 0;     //连通分量数目
    int root = 0;          //根节点数目
    bool flag = true;
    for (int i = 1; i < maxN; i++) {
        if (!visited[i]) {   //节点最大值maxN,只需访问存在于树中的节点
            continue;
        }
        if (s[i] <= 0) {     //统计图中连通分量个数
            component++;
        }
        if (inDegree[i] == 0) {    //统计根节点个数,根节点即入度为0的节点
            root++;
        }
        else if (inDegree[i] > 1) {       //某个节点的入度大于1,不符合树的定义
            flag = false;
        }
    }
    if (root != 1 || component != 1) {     //不符合树的定义
        flag = false; 
    }
    if (root == 0 && component == 0) {
        flag = true;   //空集也是树
    }
    return flag;
}

int main() 
{
    int a, b;
    int seq = 0;
    while (cin >> a && cin >> b) {
        if (a == -1 && b == -1) {    //结束测试
            break;
        }
        if (a == 0 && b == 0) {      //一组数据输入完毕
            if (IsTree()) { 
                printf("Case %d is a tree.\n", ++seq);
            }
            else {
                printf("Case %d is not a tree.\n", ++seq);
            }
            Initial();       //恢复全局变量的状态
        }
        else {
            Union(s, a, b);
            visited[a] = true;    //节点a,b存在于树中,并且节点b的入度加1
            visited[b] = true;
            inDegree[b]++;        
        }
    }
    return 0;
}