Two Graphs(全排列+二进制哈希)

题目链接

https://ac.nowcoder.com/acm/contest/139/D?&headNav=acm

题目大意

找G2中有多少子图与G1同构

解题思路

用全排列将g1中的边的端点对应到g2上,如果所有的边按照当前全排列的映射都能对应到,那么这就是一个合法情况,然后用二进制的标记当前的子图为now判重。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 110;
int n,m,mm,ans,tot,u,v;
int mpp[maxn][maxn],a[maxn];
int xx[maxn],yy[maxn];
unordered_map<int,bool>mp;
int main() {
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>mm){
        mp.clear();
        memset(mpp,0,sizeof(mpp));
        ans=tot=0;
        for(int i=1;i<=m;i++){
            cin>>xx[i]>>yy[i];
        }
        for(int i=1;i<=mm;i++){
            cin>>u>>v;
            mpp[u][v]=++tot;
            mpp[v][u]=tot;
        }
        for(int i=1;i<=n;i++){
            a[i]=i;
        }
        do{
            int now=0,flag=1;
            for(int i=1;i<=m;i++){
                int temp=mpp[a[xx[i]]][a[yy[i]]];
                if(temp==0){
                    flag=0;
                    break;
                }
                now|=(1<<temp);
            }
            if(flag&&mp[now]==0){
                mp[now]=1;
                ans++;
            }
        }while(next_permutation(a+1,a+n+1));
        cout<<ans<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注