https://ac.nowcoder.com/acm/problem/17136 题意： 给 出 n 个 点 ， m 1 条 边 表 示 图 1 ， m 2 条 边 表 示 图 2 ， 问 图 1 有 多 少 子 图 与 图 2 同 构 给出n个点，m1条边表示图1，m2条边表示图2，问图1有多少子图与图2同构 给出n个点，m1条边表示图1，m2条边表示图2，问图1有多少子图与图2同构
题解： 首 先 明 白 同 构 的 定 义 ： 当 两 图 同 构 时 ， 对 应 点 相 同 ， 对 应 边 相 同 ， 即 两 图 的 邻 接 矩 阵 相 同 。 首先明白同构的定义：当两图同构时，对应点相同，对应边相同，即两图的邻接矩阵相同。 首先明白同构的定义：当两图同构时，对应点相同，对应边相同，即两图的邻接矩阵相同。
那 么 我 们 可 以 枚 举 图 1 的 所 有 子 图 ， 即 n 个 点 的 全 排 列 ， 判 断 边 数 是 否 相 同 ， 然 后 h a s h 判 重 那么我们可以枚举图1的所有子图，即n个点的全排列，判断边数是否相同，然后hash判重 那么我们可以枚举图1的所有子图，即n个点的全排列，判断边数是否相同，然后hash判重
#include<bits/stdc++.h> using namespace std; int n,m1,m2; int e[10]; pair<int,int>p[105]; int mp[10][10]; set<unsigned long long>st; int main(){ while(cin>>n>>m1>>m2){ st.clear(); memset(mp,0,sizeof mp); for(int i = 1; i <= n; i++) e[i] = i; for(int i = 1,u,v; i <= m1; i++){ cin>>u>>v; mp[u][v] = mp[v][u] = 1; } for(int i = 1; i <= m2; i++){ cin>>p[i].first>>p[i].second; } do{ unsigned long long base = 131,ha = 0,i; int cnt = 0; for(i = 1; i <= m2; i++){ int fi = p[i].first,se = p[i].second; if(mp[e[fi]][e[se]] == 1){ cnt++; ha = ha*base+i; } } if(cnt == m1){ st.insert(ha); } }while(next_permutation(e+1,e+n+1)); cout<<st.size()<<endl; } }