5
24
2016
0

[51Nod1515] 明辨是非

维护相等的关系要用并查集

而对于不等关系,因为没有传递性我们用一个set来维护

合并时根据set的大小启发式合并就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

const int N=200005;

int n,f[N],b[N],cnt,id[N];
set<int> S[N];

struct Save{
int a,b,p;
}sav[N];

int Find(int x){return f[x]==x?x:f[x]=Find(f[x]);}

void Union(int x,int y){
if(x==y)return;
if(S[x].size()>S[y].size())swap(x,y);
for(set<int>::iterator i=S[x].begin();i!=S[x].end();i++)S[y].insert(Find(*i));
f[x]=y;
}

int main(){
freopen("1515.in","r",stdin);
freopen("1515.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&sav[i].a,&sav[i].b,&sav[i].p);
    b[++cnt]=sav[i].a;f[cnt]=cnt;
    b[++cnt]=sav[i].b;f[cnt]=cnt;
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;i++){
	sav[i].a=Find(lower_bound(b+1,b+cnt+1,sav[i].a)-b);
	sav[i].b=Find(lower_bound(b+1,b+cnt+1,sav[i].b)-b);
	if(sav[i].p){
		if(S[sav[i].b].find(sav[i].a)!=S[sav[i].b].end() || S[sav[i].a].find(sav[i].b)!=S[sav[i].a].end())puts("NO");
		else puts("YES"),Union(sav[i].a,sav[i].b);
	}
	else {
		if(sav[i].a==sav[i].b)puts("NO");
		else puts("YES"),S[sav[i].a].insert(sav[i].b),S[sav[i].b].insert(sav[i].a);
	}
}
return 0;
}
Category: 其他OJ | Tags: OI 51nod | Read Count: 441

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com