萌新求助站外题
  • 板块学术版
  • 楼主FutureThx
  • 当前回复11
  • 已保存回复11
  • 发布时间2020/10/4 21:11
  • 上次更新2023/11/5 12:00:59
查看原帖
萌新求助站外题
355559
FutureThx楼主2020/10/4 21:11

题面传送门

不知怎么错的,求大佬为蒟蒻指点一二:

#include <iostream>
#include <cstdio>
using namespace std;
int f[100010];
int find(int x){
	if(f[x] == x)
	   return x;
	return f[x] = find(f[x]);
}
int main()
{
	int u = 1,v = 1,t = 0;
	while(u != -1 && v != -1){
		scanf("%d%d",&u,&v);
		int maxn = -1;
	    if(u == 0 && v == 0){//特判 
	        cout << "No" << endl;
	        continue;
	    }
		if(u == -1 && v == -1)
		   return 0;
		bool flag[100010],xs[100010];
		for(int i = 1;i <= 100010;i++)//初始化
		    f[i] = i,flag[i] = 0,xs[i] = 0;
		do{
			xs[u] = 1;xs[v] = 1;
			if(find(u) != find(v))//不在同一集合,联通
				f[find(u)] = find(v);
			else//发现产生环 
			   t++;
			scanf("%d%d",&u,&v);
			maxn = max(u,max(v,maxn));
		}while(u != 0 && v != 0);
		if(t != 0)//发现环,输出No 
		    printf("No\n"); 
		else{
			int ts = 0;
			for(int i = 1;i <= maxn;i++){//判断是否联通 
				if(flag[find(i)] == 0 && xs[i] == 1){
				    ts++;
				    flag[find(i)] = 1;
				}
			}
			if(ts == 1)//联通,输出Yes
		       printf("Yes\n");
		    else//不连通,输出No
		       printf("No\n");
		}
		t = 0;
	}
	return 0;
}
2020/10/4 21:11
加载中...