HDU 1272(并查集求无向图环)

桃扇骨 2022-09-20 12:42 143阅读 0赞

#include <iostream>
    #include <cstring>
    using namespace std;
    
    int set[100001];
    int sum;
    int _max;
    /*
    int Find(int i)
    {
        return set[i] == 0 ? i : (set[i] = Find(set[i]));
    }
    */
    
    int Find(int i)
    {
        while (set[i] > 0)
            i = set[i];
        return i;
    }
    
    inline void Union(int son, int father)
    {
        int s = Find(son), f = Find(father);
        if (set[s] < set[f])
        {
            set[s] += set[f];
            set[f] = s;
            if (-set[s] > _max)
                _max = -set[s];
        }
        else
        {
            set[f] += set[s];
            set[s] = f;
            if (-set[f] > _max)
                _max = -set[f];
        }
    }
    
    int main()
    {
        int a, b;
        int _a, _b;
        bool ok;
        while (cin >> a >> b, ~a || ~b)
        {
            ok = true;
            sum = 0, _max = 1;
            if (!(a || b)) 
            {
                cout << "Yes" << endl;
                continue;
            }
            memset(set, -1, sizeof(set));
            if (a == b)
            {
                ok = false;
            }
            else
            {
                sum = 2;
                Union(a, b);
            }
            while (cin >> a >> b, a || b)
            {
                if (a == b)
                {
                    ok = false;
                }
                _a = Find(a), _b = Find(b);
                if (_a == _b || !ok)
                {
                    ok = false;
                    while (cin >> a >> b, a || b);
                    break;
                }
                else
                {
                    if (set[a] == -1)
                        ++sum;
                    if (set[b] == -1)
                        ++sum;
                    Union(_a, _b);
                }
            }
            if (ok && sum == _max)
                cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }