POJ——1308 HDU——Is It A Tree?（并查集模板题）

原题链接：http://poj.org/problem?id=1308

测试样例：

Sample Input

6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0
-1 -1
Sample Output

Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.

题意：给你一些点，判断是不是树。

解题思路：和杭电的1272题一模一样，只不过表达方式不一样而已，且这道题也是有向图，需要判断子结点是根结点。还有此题数据也比较刁钻，需要进行很多优化，具体看代码。指路HDU——1272题解blog：https://blog.csdn.net/hzf0701/article/details/107940984。这道题使用并查集模板即可，若对并查集还不是很熟的话，这里指路一篇blog：https://blog.csdn.net/hzf0701/article/details/107597903

AC代码：

/*
*邮箱：[e-mail]
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何问题请私信我或评论区留言，谢谢支持。
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 1e4+10;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//

int father[maxn],vis[maxn],flag,maxx;

void init()
{
    for(int i=0;i<maxn;i++)
		father[i]=i;
    memset(vis,0,sizeof(vis));
    maxx=0;
    flag=false;
}

int Find(int x)
{
	int r=x;
	while(r!=father[r])
		r=father[r];
	int i=x,j;
	while(father[i]!=r){
		j=father[i];
		father[i]=j;
		i=j;
	}
	return r;
}

void Merge(int x,int y)
{
    int fx=Find(x),fy=Find(y);
    if(y!=fy||fx==fy)//判断是否对应根节点是否相同还有就是保证子结点是根结点。
		flag=true;
    if(fx!=fy)
		father[fy]=fx;
}

int main()
{
    int kase=0;
    int u,v;
    init();
    while(~scanf("%d%d",&u,&v)&&u>=0&&v>=0)
    {
        if(u==0&&v==0)
        {
            int cnt=0;
            for(int i=1;i<=maxn;i++)
                if(vis[i]&&i==father[i]) cnt++;
            if(cnt<=1&&!flag)
                printf("Case %d is a tree.\n",++kase);
            else
                printf("Case %d is not a tree.\n",++kase);
            init();
            continue;
        }
        maxx=max(maxx,max(u,v)); //统计最大顶点编号，减少不必要的计算。
        vis[u]=vis[v]=1;
        Merge(u,v);
    }
    return 0;
}