Pjudge #21688. 图同构

题面传送门

我们考虑这个奇怪的交换方式有没有什么性质。

如果我们将每个点与其点权捆绑，可以发现这个操作方法就是每次交换使点权取反。

于是可以对每个子图分类讨论：

如果这个子图是二分图，则每个点走到目标点的路径奇偶性是固定的，则比对两个图的二元组是不是一样就好了。

如果这个子图不是二分图，则存在一个奇环，那么如果一个非环上点的颜色不对，则可以在奇数环上面绕一圈，如果一个环上的点颜色不对，则可以与相邻分别顺逆时针绕一圈，就可以调整。则答案必须要每子图都要数的种类相同，且每种颜色的奇偶性相同。

所以可以\(O(n+m)\)判即可。

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=1e6+5,M=N*4+5,K=2e3+5,mod=1000000007,Mod=mod-1;const db eps=1e-5;const int INF=1e9;
int n,m,k,x,y,z,fa[N],W[N],Fl[N],col[N],A1[N],A2[N],B1[N],B2[N];char c;vector<int> S[N];vector<pair<int,int>> I1[N],I2[N];
int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
void GA(int x,int op,int &y){if(col[x]) {if(op^col[x])y=1;return;}col[x]=op;for(int i:S[x]) GA(i,-op,y);}
void Solve(){
	int i,j;for(i=1;i<=n;i++) S[i].clear(),W[i]=fa[i]=Fl[i]=col[i]=0,I1[i].clear(),I2[i].clear();scanf("%d%d",&n,&m);for(i=1;i<=n;i++) fa[i]=i;for(i=1;i<=m;i++) scanf("%d%d",&x,&y),S[x].PB(y),S[y].PB(x),fa[GF(x)]=GF(y);
	for(i=1;i<=n;i++) !col[i]&&(GA(i,1,Fl[GF(i)]),0);for(i=1;i<=n;i++) scanf("%d",&A1[i]);for(i=1;i<=n;i++) {c=Gc();while(c<'A'||c>'Z') c=Gc();B1[i]=(c=='R');}
	for(i=1;i<=n;i++) scanf("%d",&A2[i]);for(i=1;i<=n;i++){c=Gc();while(c<'A'||c>'Z') c=Gc();B2[i]=(c=='R');}
	for(i=1;i<=n;i++) !Fl[GF(i)]&&(I1[GF(i)].PB({A1[i],B1[i]^(~col[i]?1:0)}),I2[GF(i)].PB({A2[i],B2[i]^(~col[i]?1:0)}),0);for(i=1;i<=n;i++) Fl[GF(i)]&&(I1[GF(i)].PB({A1[i],0}),I2[GF(i)].PB({A2[i],0}),W[GF(i)]^=B1[i]^B2[i]);
	for(i=1;i<=n;i++) {
		if(GF(i)^i) continue;sort(I1[i].begin(),I1[i].end());sort(I2[i].begin(),I2[i].end());for(j=0;j<I1[i].size();j++) if(I1[i][j]!=I2[i][j]){puts("NO");return;}if(W[i]){puts("NO");return ;}
	}puts("YES");
}
int main(){
	freopen("1.in","r",stdin);
	int T;scanf("%d",&T);while(T--) Solve();
}