自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 21:36:11，当前版本为作者最后更新于2020-02-25 12:16:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简化题意：给你t个无向图，依次判断它们是不是一棵完整的树

那如何判断一个无向图是不是一棵树呢？

很简单，若n个点之间有且仅有n-1条边，并且这n个点之间无环，那么这n个点组成一棵树。

划重点：n-1条边、无环

一.判断是否有n-1条边

由于每组数据都会依次给出两个点的编号，表示这两个点之间有一条边。

那我们用一个桶计算出点的个数，再用一个计数器记录连了多少条边。

判断一下边数是否等于点数-1即可。

二.判断是否有环

可以借鉴一下kruscal算法连边时判断是否形成环的方法。

用并查集维护点与点之间的联系。

每次连边时，判断两个端点是否在一个集合内。

如果在同一集合中，说明这两点已经有路径，再连边就会产生环。因此直接输出0即可。

如果不在同一集合中，说明这两点之间没有路径，可以连边。

OK，接下来是代码环节：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

inline int read(){//普通快读优化，萌新可换成cin
	int x=0,fh=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*fh;
}

const int maxn=100010;//定义数组大小
int a[maxn]; //a数组是并查集
bool flag;//flag用来记录是否出现-1,-1

int fin(int x){//查找祖先&路径压缩
	if(a[x]==0) return x;
	else return a[x]=fin(a[x]);
}

inline void check(){//判断每组数据是否是树并输出相应的答案
	memset(a,0,sizeof(a));//先清零并查集
	bool f=0;//f用来记录图中是否出现了环
	int b[maxn]={0},cnt1=0,cnt2=0,x,y,xx,yy;
	//b数组是桶，cnt1是点数，cnt2是边数 
    //x和y是连边的两点，xx和yy是两点的祖先
	while(1){//循环输入
		x=read();y=read();
		if(x==0&&y==0) break;//0,0表明输入结束
		if(x==-1&&y==-1){//-1,-1表明所有数据都已输入完
			flag=1;//flag记录一下
			return;//直接返回主函数
		}
		if(f) continue;
        //已经有环了，那就不用再进行操作了
        //这里是为了节省空间，因为还得把剩下的数据输入
        //如果不用f标记的话必须得用数组存储
		xx=fin(x);yy=fin(y);//查找祖先
		if(xx!=yy){//祖先不同，不在同一集合中
			a[xx]=yy;//连边
			if(!b[x]){//x这个点之前没出现过
				b[x]=1;//修改桶
				cnt1++;//点数+1
			}
			if(!b[y]){//同上
				b[y]=1;
				cnt1++;
			}
			cnt2++;//又连了一条边，因此边数要+1
		}else{//祖先相同，在同一集合中
			f=1;//出现了环，更改f标记
		}
	}
	if(cnt2==cnt1-1&&!f) printf("1\n");
    //边数是点数-1且无环，是树，输出1
	else printf("0\n");
    //否则不是树，输出0
	return;
} 

int main(){
	while(1){
		check();
		if(flag) break;
        //出现了-1，-1，所有数据已输入完毕，跳出循环
	}
	return 0;
}

你AC了没？AC了就给个赞呗。