并查集 HDU 1272 小希的迷宫

先找了几题练练，都是套模板，但这题卡住了，一直找不到原因，后来看了别人解题报告，才明白忽略了一个问题

题意是：给你一幅图，判断它是否存在回路

要注意：要考虑图拆分为几颗树时，也是不符合的。一开始没考虑到这个问题

#include <iostream>
#define MAX 100005
using namespace std;

int parent[MAX];


void Union2(int, int);
int find2(int);

int main()
{
        int n, m;
        int a,b;
        int root_a, root_b;
        int flag;
        //freopen("C:\\Users\\Haojian\\Desktop\\test.txt", "r", stdin);
        scanf("%d%d",&a, &b);
        while ( a != -1 && b != -1)
        {
                memset(parent, -1, MAX*sizeof(int));
                flag = true;
                m = 0;
                n = a;
                while (a||b)
                {               
        
                        if (parent[a-1] == -1 && parent[b-1] == -1)
                                m++;
                        else if (parent[a-1] != -1 && parent[b-1] != -1)
                                m--;
                                
                        //查找根结点
                        root_a = find2(a-1);
                        root_b = find2(b-1);

                        //如果两个根节点相同，证明a,b两点已有路相连，再添加边会产生回路
                        if (root_a != root_b)           
                                Union2(root_a, root_b);
                        else
                                flag = false;
                        scanf("%d%d",&a, &b);
                }
                if (flag && m == 1 || n == 0)
                        cout << "Yes" << endl;
                else
                        cout << "No" << endl;
                scanf("%d%d",&a, &b);
        }
        return 0;
}

//并集，根节点多的做根节点少的父节点
void Union2(int i , int j)
{       
        int temp = parent[i] + parent[j];
        if (parent[i] > parent[j])
        {
                parent[i] = j;
                parent[j] = temp;
        }
        else
        {
                parent[j] = i;
                parent[i] = temp;
        }

}

//查找，运用折叠规则
int find2(int i)
{
        int root, trail,lead;
        for (root = i; parent[root] >= 0; root = parent[root])
                ;
        for (trail = i; trail != root; trail = lead)
        {
                lead = parent[trail];
                parent[trail] = root;
        }
        return root;
}