连样例都没过求助
查看原帖
连样例都没过求助
717476
Gaochenxi103_QWQ楼主2023/8/8 23:34

萌新第一次写带权并查集的题目

连样例都没过

求助给我大佬讲一下

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N],vis[N];
int n,k;
int ans=0;
int find(int a)
{
	if (a!=f[a]) 
	{
		int fa=find(f[a]);
   		vis[a]=(vis[a]+vis[fa])%3;   
   		return f[a]=fa;
   	}
   return f[a];
}
bool m(int num,int a,int b)
{
	int fa=find(a),fb=find(b);
	if(num==1)
	{
		if(fa==fb and vis[a]!=vis[b])
		{
			return false;
		}
		if(fa!=fb)
		{
			f[fa]=fb;
			vis[fa]=(3-vis[a]+vis[b])%3;
			return true;
		}
	}
	if(fa==fb)
	{
		if(abs(vis[a]-vis[b])%3!=1)
		{
			return false;
		}
	}
	f[fa]=fb;
	vis[fa]=(3-vis[a]+vis[b]+1)%3;
	return true;
}
int main()
{
	cin>>n>>k;
	int num,x,y;
	for(int i=1;i<=n;i++) f[i]=i,vis[i]=0;
	for(int i=1;i<=k;i++)
	{
		cin>>num>>x>>y;
		if(x>n or y>n or (num==2 and x==y) or !m(num,x,y))
		{
			ans++;
			continue;
		}
	}
	cout<<ans;
}

求助!

2023/8/8 23:34
加载中...