什么是同构(无向完全图有几种非同构的圈)

大家好，又见面了，我是你们的朋友全栈君。

http://162.105.81.212/JudgeOnline/problem?id=2040  

题意给定两个有向图，找出其同构的对应点，并输出其对应的序列。。。

介于 该题的点数 <= 25 个 直接dfs搜索就可以解决问题，但是剪掉还是必要的；

1 ， 对于在途中的出度 和 入读 都唯一的点，那么就可以直接的判断其对应关系，

2 ， 对于当前点u， 他与 已经 确定对应关系的点 i 的关系 必须 和 正准备和u匹配的点 v 和 点dict1[i].match 的关系相等 ；

如果不相等 ，那么必须剪枝。。。。

条件：

    if(map1[u][i] != map2[v][dict1[i].match] ||map1[i][u] != map2[dict1[i].match][v])   

/*<br /> Name:<br /> Copyright:<br /> Author:<br /> Date: 07-01-02 00:35<br /> Description:<br />*/<br /> Problem: 2040 User: yuhailin<br /> Memory: 224K Time: 0MS<br /> Language: C++ Result: Accepted<br />#include <iostream><br />#include <algorithm><br />#include <string><br />using namespace std ;<br />#define clr(c) memset(c,0,sizeof(c))<br />struct Node {<br /> string word ;<br /> int match ;<br />};<br />int m, n1, n2, in1[30], out1[30], in2[30], out2[30], map1[30][30], map2[30][30];<br />Node dict1[30], dict2[30] ;<br />int find(Node *dict, string str, int n) {<br /> for(int i = 0; i < n; i ++) {<br /> if(dict[i].word == str)<br /> return i ;<br /> }<br /> return -1 ;<br />}<br />void Init() {<br /> string t1, t2 ;<br /> n1 = n2 = 0 ;<br /> int a,b ;<br /> clr(map1), clr(map2), clr(in1), clr(out1), clr(in2), clr(out2) ;<br /> for(int i=0; i < m; i++) {<br /> cin >> t1 >> t2 ;<br /> a = find(dict1, t1, n1) ;<br /> if(a == -1) {<br /> a = n1 ;<br /> dict1[n1].word = t1, dict1[n1++].match = -1 ;<br /> }<br /> b = find(dict1, t2, n1) ;<br /> if(b == -1) {<br /> b = n1 ;<br /> dict1[n1].word = t2, dict1[n1++].match = -1 ;<br /> }<br /> map1[a][b] = 1 ;<br /> in1[b]++, out1[a]++ ;<br /> }<br /> for(int i=0; i<m; i++) {<br /> cin >> t1 >> t2 ;<br /> a = find(dict2, t1, n2) ;<br /> if(a == -1) {<br /> a = n2 ;<br /> dict2[n2].word = t1, dict2[n2++].match = -1 ;<br /> }<br /> b = find(dict2, t2, n2) ;<br /> if(b == -1) {<br /> b = n2 ;<br /> dict2[n2].word = t2, dict2[n2++].match = -1 ;<br /> }<br /> map2[a][b] = 1 ;<br /> in2[b]++, out2[a]++ ;<br /> }<br />}<br />void Attend_uniqe() {<br /> int ret, k;<br /> for(int i = 0 ; i < n1 ; i++) {<br /> ret = 0;<br /> for(int j=0;j<n2;j++) {<br /> if(in1[i] == in2[j] && out1[i] == out2[j]) {<br /> ret ++ ;<br /> k = j ;<br /> }<br /> }<br /> if(ret == 1)<br /> dict1[i].match = k, dict2[k].match = i ;<br /> }<br />}<br />bool df_search(int u) {<br /> if(u < 0)<br /> return true ;<br /> if(dict1[u].match != -1)<br /> return df_search(u-1) ;<br /> for(int v = 0; v < n2 ; v++) {<br /> if(dict2[v].match != -1) continue ;<br /> if(in1[u] == in2[v] && out1[u] == out2[v]) {<br /> bool ok = 0 ;<br /> for(int i=0; i<n1; i++) {<br /> if(i == u || dict1[i].match == -1) continue ;<br /> if(map1[u][i] != map2[v][dict1[i].match] ||map1[i][u] != map2[dict1[i].match][v]) ok = 1 ;<br /> }<br /> if(ok == 0) {<br /> dict1[u].match = v, dict2[v].match = u ;<br /> if(df_search(u-1)) return true ;<br /> dict1[u].match = dict2[v].match = -1 ;<br /> }<br /> }<br /> }<br /> return false ;<br />}<br />int cmp(const Node a, const Node b) {<br /> return a.word < b.word ;<br />}<br />void print() {<br /> sort(dict1, dict1+n1, cmp) ;<br /> for(int i=0; i<n1; i++)<br /> cout<< dict1[i].word <<“/” << dict2[dict1[i].match].word << endl ;<br /> cout << endl ;<br />}<br />int main()<br />{<br /> while(cin >> m && m) {<br /> Init() ;<br /> Attend_uniqe() ;<br /> df_search(n1 – 1) ;<br /> print() ;<br /> }<br /> return 0;<br />}<br />