Graph theory terms, assuming G=(V,E) and G1=(V1, E1) are two graphs, if there is a bijective m: V→V1, such that all x and y∈V have xy∈E equivalent to m(x)m(y)∈E1, then G and G1 are isomorphism. Such a mapping M is called an isomorphism. If G=G1, it is called an automorphism.
Simply put, the same composition must have the same number of knots and the same structure.
In Figure 3.6, the difference between the first figure and the second figure is the number of rings. The first figure is one ring and the second is two rings, so it is not an isomorphism.
If you delete Z1 and U1, if you delete v1 and w1, if you join Z1 and W1, and you form a chain of V1U1 and a ring of Z1W1x1y1, it’s still not an isomorphism, because you have to have the same number of rings and the same number of chains.
For example, there are two rings A1 and A2 in figure A, a1 has 3 nodes, A2 has 5 nodes, figure B also has two rings, B1 has 4 nodes, B2 has 4 nodes, it is still not isomorphic, the condition here is that the number of borrowing points on the ring or chain is the same, regardless of the order of nodes.
Introduce the example, hDU3926-hand in Hand, to judge whether the graph formed twice is an isomorphic composition.
One idea: through and look up the set to determine the number of rings/chains, and the number of rings/chains, and then sort for comparison.
Sort by number of users. If the number of users is the same, sort by status. It might be easier to pay attention to these points.
Try it yourself, and then refer to the code.
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<math.h> 5 #include<vector> 6 #include<algorithm> 7 #include<queue> 8 #include<set> 9 using namespace std; 10 int pre[10100]; 11 struct e{ 12 int a,b; 13}; 14 e s1[10010]; 15 e s2[10010]; 16 int find(int x) 17 { 18 while(x! =pre[x]) 19 x=pre[x]; 20 return x; 21 } 22 int cmp(e a,e b){ 23 if(a.a==b.a) return a.b>b.b; 24 else return a.a>b.a; 25 } 26 void init(int n) 27 { 28 for(int i=1; i<=n; i++) 29 pre[i]=i; 30 } 31 int main() 32 { 33 int t,cas=1;; 34 scanf("%d",&t); 35 while(t--) 36 { 37 for(int i=1; i<10010; i++) 38 { 39 s1[i].a=1; s1[i].b=0; 40 s2[i].a=1; s2[i].b=0; } 42 bool flag=false; 43 int n1,m1,n2,m2; 44 45 scanf("%d%d",&n1,&m1); 46 init(n1); 47 for(int i=0; i<m1; i++) 48 { 49 int a,b; 50 scanf("%d%d",&a,&b); 51 int dx=find(a); 52 int dy=find(b); 53 if(dx! =dy) 54 { 55 pre[dx]=dy; 56 s1[dy].a+=s1[dx].a; 57 s1[dx].a=0; } 59 else s1[dy]. B =1; } 61 62 scanf("%d%d",&n2,&m2); 63 init(n2); 64 for(int i=0; i<m2; i++) 65 { 66 int a,b; 67 scanf("%d%d",&a,&b); 68 int dx=find(a); 69 int dy=find(b); 70 if(dx! =dy) 71 { 72 pre[dx]=dy; 73 s2[dy].a+=s2[dx].a; 74 s2[dx].a=0; 75 } 76 else s2[dy].b=1; 77 } 78 if(n1==n2){ 79 80 sort(s1+1,s1+n1+1,cmp); 81 sort(s2+1,s2+n2+1,cmp); 82 83 for(int I =0; i<n1; i++) 84 if(s1[i].a! =s2[i].a||s1[i].b! =s2[I].b) {// Check the number of status 85 flag=true; 86 break; 87 } 88 } 89 if(n1! =n2) flag=true; 90 91 if(flag) printf("Case #%d: NO\n",cas++); 92 else printf("Case #%d: YES\n",cas++); 93 } 94 return 0; 95}Copy the code