HDU1272小希的迷宫并查集确定图为树

这题主要是解决一个图是否是树的问题。
有很多细节需要注意。
1、空树也是树。
2、一个图若是树需满足两个条件：
①连通分量为一；
②图中无环，包括自环和非自环。
3、边数+1=顶点数。

AC代码：
[cpp]
#include<iostream>
using namespace std;

const int MAX=100001;
int father[MAX];
bool flag[MAX],flagLC;

void initial()    //初始化
{
    for(int i=1;i<MAX;i++)
        father[i]=i;
}

int find(int x)    //查找
{
    while(father[x]!=x)
        x=father[x];

    return x;
}

void combine(int a,int b)   //合并
{
    int tmpa=find(a);
    int tmpb=find(b);

    if(tmpa!=tmpb)
        father[tmpa]=tmpb;
    else
        flagLC=true;    //a,b在同一个连通分量中，说明有环
}

int main()
{
    int i,a,b,connectedComponent,edgeNum,nodeNum;
    bool flagCircle; //自环

    while(1)
    {
        initial();
        edgeNum=0; //边数
        flagLC=flagCircle=false;   //标志是否有环
        memset(flag,false,sizeof(flag));   //标志在图内的点，在为true

        scanf("%d%d",&a,&b);

        if(a==0 && b==0)   //空树
        {
            cout<<"Yes"<<endl;
            continue;
        }

        if(a==-1 && b==-1) break;
        if(a==b) flagCircle=true;

        flag[a]=true;
        flag[b]=true;
        edgeNum++;
        combine(a,b);

        while(1)
        {
            scanf("%d%d",&a,&b);
            if(a==0 && b==0) break;
            if(a==b) flagCircle=true;

            flag[a]=true;
            flag[b]=true;
            edgeNum++;
            combine(a,b);
        }

        connectedComponent=0;        //连通分量数
        nodeNum=0;    //点数
        for(i=1;i<MAX;i++)   //判断图是否连通，tmp=1连通
        {
            if(flag[i])
            {
                nodeNum++; //计算图内包含的所有点
                if(father[i]==i)
                    connectedComponent++;
            }
        }    www.zzzyk.com

        if(connectedComponent==1 && nodeNum==edgeNum+1 && !flagCircle && !flagLC) //连通的无环图为树
            cout<<"Yes";
        else
            cout<<"No";
        cout<<endl;
    }

    return 0;
}

作者：Lulipeng_cpp

补充：软件开发 , C++ ,

HDU1272小希的迷宫 并查集确定图为树

HDU1272小希的迷宫并查集确定图为树