玄学80分,萌新求调!!!
查看原帖
玄学80分,萌新求调!!!
698678
zlinda楼主2023/3/31 22:39

错在2和8,下载了2的数据,看了半天找不出错在哪,求大佬找错,代码清晰可读!!!

#include<bits/stdc++.h>
using namespace std;
int t,n,top,ans,fa[200100];
struct hhh
{
	int x,y;
	bool op;
} v[100010];
map<int,int> M;
int find(int z)//寻找祖先 
{
    if(fa[z]==z) return z;
    else return fa[z]=find(fa[z]);//路径压缩 
}
void add(int z,int y)//将两个集合合并 
{
	z=find(z);
	y=find(y);
    fa[z]=y;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("1955.in","r",stdin);
	cin>>t;
	for(int j=1;j<=t;j++)
	{
		for(int i=1;i<=2*n+5;i++) fa[i]=i;
		top=0; ans=0;
		M.clear();//map一定要清空!!! 
		cin>>n;
		for(int i=1;i<=n;i++) 
		{
			cin>>v[i].x>>v[i].y>>v[i].op;
			if(!M.count(v[i].x))
			{
				top++;
				M[v[i].x]=top;
			}
			if(!M.count(v[i].y))
			{
				top++;
				M[v[i].y]=top;
			}
			if(v[i].op)//先把相等的合并 
				add(find(M[v[i].x]),find(M[v[i].y]));
		}
		for(int i=1;i<=n;i++)
		{
			if(!v[i].op)//判断是否冲突 
				if(find(M[v[i].x])==find(M[v[i].y])) 
				{
					ans=1;
					break;
				}
		}
		if(ans) cout<<"NO"<<'\n';
		else cout<<"YES"<<'\n';
	}
	return 0;
}
2023/3/31 22:39
加载中...