AT_abc232_c 题解

ikunTLE · 2024-12-17 22:02:16 · 题解

题目传送门

思路

由于 N\le8，可以用全排列解决此题。

先用邻接矩阵存储图，设两个图分别为 A 和 B。初始化 P_i=i，然后对它进行全排列，代表着 A_{i,j} 对应 B_{P_{i},P_{j}}。如果 P 在某种排列下，所有的 A_{i,j} 全部满足 A_{i,j}=B_{P_{i},P_{j}}，那么有解。否则在所有的情况下都不满足，则无解。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=10;
bool a[N][N],b[N][N];
int n,m,p[N];
bool check(){
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(a[i][j]!=b[p[i]][p[j]])
                return false;
    return true;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        a[u][v]=a[v][u]=true;
    }
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        b[u][v]=b[v][u]=true;
    }
    for(int i=1;i<=n;++i)
        p[i]=i;
    do{
        if(check())
            return printf("Yes\n"),0;
    }while(next_permutation(p+1,p+n+1));
    printf("No\n");
    return 0;
}