Lvat_s Blog

首先树同构我是写过的……就是BJOI那题

然后图同构我是不会的……

然后就花了点头盾看了题解。

原来和树Hash差不多，只要进行迭代就好了

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

const int M=4005,N=205;
const long long P1=808080808080803ll,P2=888888888888887ll;

int n,m,hA[N],hB[N],enA,enB,test;
long long valA_1[N],valB_1[N],valA_2[N],valB_2[N],tmp1[N],tmp2[N],Vt1[N],Vt2[N];

struct Edge{
int b,next;
}eA[M<<1],eB[M<<1];

void AddEdgeA(int sa,int sb){
eA[++enA].b=sb;
eA[enA].next=hA[sa];
hA[sa]=enA;
}

void AddEdgeB(int sa,int sb){
eB[++enB].b=sb;
eB[enB].next=hB[sa];
hB[sa]=enB;
}

void Solve_A(){
for(int i=1;i<=n;i++){
	int cnt=0;
	for(int j=hA[i];j;j=eA[j].next){
		int v=eA[j].b;cnt++;
		tmp1[cnt]=valA_1[v];
		tmp2[cnt]=valA_2[v];
	}
	sort(tmp1+1,tmp1+cnt+1);
	sort(tmp2+1,tmp2+cnt+1);
	long long Ha1=0,Ha2=0;
    for(int j=1;j<=cnt;j++){Ha1=(Ha1*233ll+tmp1[j])%P1;Ha2=(Ha2*666ll+tmp2[j])%P2;}
    Vt1[i]=Ha1;Vt2[i]=Ha2;
}
for(int i=1;i<=n;i++){valA_1[i]=Vt1[i];valA_2[i]=Vt2[i];}
}

void Solve_B(){
for(int i=1;i<=n;i++){
	int cnt=0;
	for(int j=hB[i];j;j=eB[j].next){
		int v=eB[j].b;cnt++;
		tmp1[cnt]=valB_1[v];
		tmp2[cnt]=valB_2[v];
	}
	sort(tmp1+1,tmp1+cnt+1);
	sort(tmp2+1,tmp2+cnt+1);
	long long Ha1=0,Ha2=0;
    for(int j=1;j<=cnt;j++){Ha1=(Ha1*233ll+tmp1[j])%P1;Ha2=(Ha2*666ll+tmp2[j])%P2;}
    Vt1[i]=Ha1;Vt2[i]=Ha2;
}
for(int i=1;i<=n;i++){valB_1[i]=Vt1[i];valB_2[i]=Vt2[i];}
}

void Solve(){
scanf("%d %d",&n,&m);
memset(hA,0,sizeof(hA));
memset(hB,0,sizeof(hB));
enA=0;enB=0;
for(int i=1;i<=m;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdgeA(u,v);AddEdgeA(v,u);
}
for(int i=1;i<=m;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdgeB(u,v);AddEdgeB(v,u);
}
for(int i=1;i<=n;i++)valA_1[i]=valA_2[i]=valB_1[i]=valB_2[i]=1;
for(int i=1;i<=n;i++)Solve_A();
for(int i=1;i<=n;i++)Solve_B();
sort(valA_1+1,valA_1+n+1);
sort(valA_2+1,valA_2+n+1);
sort(valB_1+1,valB_1+n+1);
sort(valB_2+1,valB_2+n+1);
int flag=1;
for(int i=1;i<=n;i++)if(valA_1[i]!=valB_1[i] || valA_2[i]!=valB_2[i]){puts("NO");flag=0;break;}
if(flag)puts("YES");
}

int main(){
freopen("1676.in","r",stdin);
freopen("1676.out","w",stdout);
scanf("%d",&test);
while(test--)Solve();
return 0;
}

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

而对于不等关系，因为没有传递性我们用一个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;
}