专栏首页小樱的经验随笔图论----同构图(详解)

图论----同构图(详解)

图论当中的术语,假设G=(V,E)和G1=(V1,E1)是两个图,如果存在一个双射m:V→V1,使得对所有的x,y∈V均有xy∈E等价于m(x)m(y)∈E1,则称G和G1是同构的,这样的一个映射m称之为一个同构,如果G=G1,则称他为一个自同构。

简单来说,同构图的结点数必须相同,结构必须相同。

如图3.6,第一个图形和第二个图形的区别在于环的数量。第一个图形为一个环,第二个为两个环,所以不是同构图。

若删去z1和u1,删去v1和w1,连接z1和w1,成为一个v1u1的链和z1w1x1y1的环,依旧不是同构图,因为必须环数相同,链数相同。

但这还是缺少一个条件,比如图形A存在两个环a1和a2,a1有3个结点,a2有5个结点,图形B也有两个环,b1有4个结点,b2有4个结点,依旧不是同构图,这里的条件就是环上或链上的借点数相同,和结点顺序无关。

引入例题,HDU3926-Hand in Hand ,判断两次组成的图形是否是同构图。

思路之一:通过并查集确定环数/链数,和环内/链内的人数,再排序进行比较。

排序时按照人数排序,若人数相同要按照状态排序。注意这几点或许会比较容易过。

请先自己进行尝试,尝试后再参考代码。

 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;//最开始每个都是独立的,默认为链  
41             }  
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;//把拉手的孩子数量加起来,下同  
58                 }  
59                 else s1[dy].b=1;//成环  
60             }  
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) {//判断数量,状态  
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     }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题,n^4大暴力】

    1800: [Ahoi2009]fly 飞行棋 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1689  So...

    Angel_Kitty
  • 最长递减子序列(nlogn)(个人模版)

    最长递减子序列(nlogn): 1 int find(int n,int key) 2 { 3 int left=0; 4 int ri...

    Angel_Kitty
  • 并查集(个人模版)

    并查集: 1 int find(int a) 2 { 3 int r=a; 4 while(f[r]!=r) 5 ...

    Angel_Kitty
  • Java入门 - 面向对象 - 01.继承

    原文地址:http://www.work100.net/training/java-inheritance.html

    光束云
  • P1181 数列分段Section I

    题目描述 对于给定的一个长度为N的正整数数列A[i],现要将其分成连续的若干段,并且每段和不超过M(可以等于M),问最少能将其分成多少段使得满足要求。 输入输出...

    attack
  • BZOJ2023: [Usaco2005 Nov]Ant Counting 数蚂蚁(dp)

    有一个小trick:在处理前缀和的时候我们可以保留下本层dp的信息,所以滚动数组是不需要的,具体看代码吧

    attack
  • LintCode-44. 最小子数组

    悠扬前奏
  • LintCode-41. 最大子数组

    给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为6

    悠扬前奏
  • 【DB笔试面试632】在Oracle中,如何锁住统计信息?

    Oracle会自动收集表的统计信息,大部分情况下,这种行为是有利的。当不需要对某个表做收集的时候,可以采用锁定统计信息的方法,把不需要收集的表排除在外,这样可以...

    小麦苗DBA宝典
  • cf932E. Team Work(第二类斯特灵数 组合数)

    $$m^n = \sum_{i = 0}^m C_{n}^i S(n, i) i!$$

    attack

扫码关注云+社区

领取腾讯云代金券