Poj 3310 Caterpillar (并查集判环+度)

r囧r小猫 2022-08-27 03:53 124阅读 0赞

题意：判断一个给定的图是否满足以下条件：

1.没有环

2.而且存在一条链，图上的所有点均在链上，或者是链上点的邻居。

解题思路：

1.要求存在一条链，那么图必须连通，可以在判断环时用并查集一并解决，详见代码。

2.判断点的位置是否满足：首先统计各个点的度，对于度为1的点，将其相连的边删掉，再统计新图的度，这时新图应该剩下一条链，也就是说，新图度为1的点应该只有两个，而且这个点在旧图的度是大于1的。

#include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    
    const int MAX=105;
    
    class Disjoint_Set
    {
    public:
    	int father[MAX];            /*father[x]表示x的父节点*/
    	int rank[MAX];              //以该节点为根节点的点数,同时起到按秩合并的作用
    
    	void Init (int n)
    	{
    		for (int i=0;i<=n;i++)
    			Make_Set (i);
    	}
    
    	void Make_Set (int x)
    	{
    		father[x]=x;
    		rank[x]=1;
    	}
    
    	int Find_Set (int x)
    	{
    		if (x != father[x])
    			father[x] = Find_Set(father[x]);//回溯
    		return father[x];
    	}
    
    	bool Union (int x,int y)
    	{//返回false表示要合并的两点已在同一个集合中
    		int a=Find_Set (x);
    		int b=Find_Set (y);
    		if (a == b)
    			return false;
    		if (rank[a] >= rank[b])
    		{
    			father[b]=a;
    			rank[a]+=rank[b];
    		}
    		else
    		{
    			father[a]=b;
    			rank[b]+=rank[a];
    		}
    		return true;
    	}
    }ob;
    
    vector<int> graphs[MAX];
    int predeg[MAX]; //统计每个点原来的度
    int degree[MAX];
    int n,m;
    
    bool Deal ()
    {
        int i;
        for (i=1;i<=n;i++)
            if (predeg[i]==1)
                for (int j=0;j<graphs[i].size();j++)
                    degree[graphs[i][j]]--;
    
        int cnt=0;
        for (i=1;i<=n;i++)
            if (predeg[i]>1 && degree[i]==1)  //注意需要predeg[i]>1
                cnt++;
        if (cnt>2) return false;
        return true;
    }
    
    int main ()
    {
    	int Cas=1;
    	while (~scanf("%d%d",&n,&m),n)
        {
    		ob.Init(MAX);
    		memset(predeg,0,sizeof(predeg));
    		memset(degree,0,sizeof(degree));
    		int cnt=0;
    		bool flag=true;
    		if (n!=m+1) flag=false;  //无环必须满足
    		for (int i=0;i<m;i++)
    		{
    		    int a,b;
    		    scanf("%d%d",&a,&b);
    		    predeg[a]++,degree[a]++;
                predeg[b]++,degree[b]++;
                graphs[a].push_back(b);
                graphs[b].push_back(a);
    		    if (ob.Union(a,b)==false)
                    flag=false;  //若u和v的根节点相同，并且他们又彼此连通，则说明构成环
    		}
    		if (flag) //无环且所有点连通（无环且 点数-1==边数 则说明只有一个连通块）
            {//或者可以循环判断每个点的根节点是否相同
                if (Deal ())
                    printf("Graph %d is a caterpillar.\n",Cas++);
                else
                    printf("Graph %d is not a caterpillar.\n",Cas++);
            }
            else
                printf("Graph %d is not a caterpillar.\n",Cas++);
    	}
    	return 0;
    }