双射 - hash去重

题目描述
Two undirected simple graphs and where are isomorphic when there exists a bijection on V satisfying if and only if {x, y} ∈ E2.
Given two graphs and , count the number of graphs satisfying the following condition:
* .
* G1 and G are isomorphic.
输入描述:

The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains three integers n, m1 and m2 where |E1| = m1 and |E2| = m2.
The i-th of the following m1 lines contains 2 integers ai and bi which denote {ai, bi} ∈ E1.
The i-th of the last m2 lines contains 2 integers ai and bi which denote {ai, bi} ∈ E2.

输出描述:

For each test case, print an integer which denotes the result.

示例1
输入

3 1 2
1 3
1 2
2 3
4 2 3
1 2
1 3
4 1
4 2
4 3

输出

2
3

备注:

* 1 ≤ n ≤ 8
*
* 1 ≤ ai, bi ≤ n
* The number of test cases does not exceed 50.

题意 : 给你两个大小为 N 的图，要求寻找既是B的子图，又和A是同构的图的数量

思路分析：刚开始一直不是很懂它的题意是要干嘛，比赛后也看了很长时间才懂一些，1-2 3 和 1 2-3 是属于同构关系的，因为都是两个点连着，一个点单独出现，因此这里只要N！枚举对应一下就可以了

1 . hash去判重

#include <bits/stdc++.h>

using namespace std;

#define ll unsigned long long

const ll maxn = 1e6+5;

const ll mod = 1e9+7;

const double eps = 1e-9;

const double pi = acos(-1.0);

const ll inf = 0x3f3f3f3f;

ll n, m1, m2;

bool mp1[10][10], mp2[10][10];

ll arr[10], d[10];

set<ll>s;

void solve() {

    for(ll i = 1; i <= n; i++) arr[i] = i;

    do{

        for(ll i = 1; i <= n; i++) d[i] = arr[i];

        ll sum = 0;

        for(ll i = 1; i <= n; i++){

            for(ll j = i+1; j <= n; j++){

                if (mp2[i][j] && mp1[d[i]][d[j]]){

                    sum++;

                }

            }

        }

        if (sum == m1){

            ll x = 0;

            for(ll i = 1; i <= n; i++){

                for(ll j = i+1; j <= n; j++){

                    if (mp1[d[i]][d[j]]) {

                        x+=(1LL<<(i*(n-1)+j));

                    }

                }

            }

            //printf("++++ %llu \n", x);

            s.insert(x);

        }

    }while(next_permutation(arr+1, arr+1+n));

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    ll a, b;

    while(~scanf("%d%d%d", &n, &m1, &m2)){

        memset(mp1, false, sizeof(mp1));

        memset(mp2, false, sizeof(mp2));

        for(ll i = 1; i <= m1; i++){

            scanf("%d%d", &a, &b);

            mp1[a][b] = mp1[b][a] = true;

        }

        for(ll i = 1; i <= m2; i++){

            scanf("%d%d", &a, &b);

            mp2[a][b] = mp2[b][a] = true;

        }

        s.clear();

        solve();

        printf("%d\n", s.size());

    }

    return 0;

}

2 . 直接这样考虑，就是A图自身的同构在通过B去计算的时候，会重复算的，因此除一下就可以了

using namespace std;

#define ll unsigned long long

const ll maxn = 1e6+5;

const ll mod = 1e9+7;

const double eps = 1e-9;

const double pi = acos(-1.0);

const ll inf = 0x3f3f3f3f;

ll n, m1, m2;

bool mp1[10][10], mp2[10][10];

ll arr[10], d[10];

set<ll>s;

int a1, a2;

void solve() {

    for(ll i = 1; i <= n; i++) arr[i] = i;

    do{

        for(ll i = 1; i <= n; i++) d[i] = arr[i];

        ll sum = 0;

        for(ll i = 1; i <= n; i++){

            for(ll j = i+1; j <= n; j++){

                if (mp2[i][j] && mp1[d[i]][d[j]]){

                    sum++;

                }

            }

        }

        if (sum == m1){

            a1++;

        }

    }while(next_permutation(arr+1, arr+1+n));

}

void solve2() {

    for(ll i = 1; i <= n; i++) arr[i] = i;

    do{

        for(ll i = 1; i <= n; i++) d[i] = arr[i];

        ll sum = 0;

        for(ll i = 1; i <= n; i++){

            for(ll j = i+1; j <= n; j++){

                if (mp1[i][j] && mp1[d[i]][d[j]]){

                    sum++;

                }

            }

        }

        if (sum == m1){

            a2++;

        }

    }while(next_permutation(arr+1, arr+1+n));

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    ll a, b;

    while(~scanf("%d%d%d", &n, &m1, &m2)){

        memset(mp1, false, sizeof(mp1));

        memset(mp2, false, sizeof(mp2));

        for(ll i = 1; i <= m1; i++){

            scanf("%d%d", &a, &b);

            mp1[a][b] = mp1[b][a] = true;

        }

        for(ll i = 1; i <= m2; i++){

            scanf("%d%d", &a, &b);

            mp2[a][b] = mp2[b][a] = true;

        }

        s.clear();

        a1 = a2 = 0;

        solve();

        solve2();

        printf("%d\n", a1/a2);

    }

    return 0;

}

巴特西

双射 - hash去重

最新文章

热门文章