• 【图论】二分图染色

    知识点

    一 . 定义

    二分图有个性质，如果一个图不是二分图，那么就一定有奇环；如果没有奇环，就一定是二分图

    一 . 二分图染色法

    例题：

    CF741C Arpa’s overnight party and Mehrdad’s silent entering

    题目描述

    有2n个人围成一圈坐在桌子边上，每个人占据一个位子，对应这2n个人是n对情侣，要求情侣不能吃同一种食物，并且桌子上相邻的三个人的食物必须有两个人是不同的，只有两种食物（1或者是2），问一种可行分配方式。

    输入格式

    第一行为客人数量

    接下来n行，第i+1行表示第i对情侣男女坐的位置

    输出格式

    无解输出-1

    否则输出n行，第i+1行分别为第i组男女所食的种类

    如果有多组解，输出任意一组解（spj）

    输入输出样例

    输入 #1

    3
1 4
2 5
3 6

    输出 #1

    1 2
2 1
1 2
    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. int n;
    7. bool check=0;
    8. const int maxn=1e6+5;
    9. struct node{
    10. 	int to,next;
    11. }edge[maxn<<1];
    12. int head[maxn],num=0,colour=1;
    13. int col[maxn],a[maxn],b[maxn];
    14. inline int read()
    15. {
    16. 	int x=0,f=1;
    17. 	char c=getchar();
    18. 	while(c<'0'||c>'9')
    19. 	{
    20. 		if(c=='-') f=-1;
    21. 		c=getchar();
    22. 	}
    23. 	while(c>='0'&&c<='9')
    24. 	{
    25. 		x=(x<<3)+(x<<1)+(c^48);
    26. 		c=getchar();
    27. 	}
    28. 	return x*f;
    29. }
    30.  
    31. inline void add(int u,int v)
    32. {
    33. 	edge[++num].to=v;
    34. 	edge[num].next=head[u];
    35. 	head[u]=num;
    36. }
    37.  
    38. inline void dfs(int u,int colour)  //二分图的染色
    39. {
    40. 	col[u]=colour; 
    41. 	for(int i=head[u];i!=-1;i=edge[i].next)
    42. 	{
    43. 		int v=edge[i].to;
    44. 		if(col[v]) continue;
    45. 		dfs(v,3-colour); //与该点相连的点染成不同的颜色
    46. 	}
    47. }
    48.  
    49. int main()
    50. {
    51. 	n=read();
    52. 	memset(head,-1,sizeof(head));
    53. 	memset(col,0,sizeof(col));
    54. 	for(int i=1;i<=n;++i)
    55. 	{
    56. 		a[i]=read(); b[i]=read();
    57. 		add(a[i],b[i]); //先将情侣之间相互连线
    58. 		add(b[i],a[i]);
    59. 		add(i<<1,i<<1|1); //又因为要求2i和2i+1食物类型不同，相邻的两个点也要染成不同颜色
    60. 		add(i<<1|1,i<<1);
    61. 	}
    62. 	for(int i=1;i<=(n<<1);++i)
    63. 	{
    64. 		if(!col[i])	dfs(i,1); //一般二分图染色分别为1和2，0代表未染色
    65. 	}
    66. 	for(int i=1;i<=n;++i)
    67. 	{
    68. 		printf("%d %d\n",col[a[i]],col[b[i]]);
    69. 	}
    70. 	return 0;
    71. }

    相关练习

    （待填坑）1. 洛谷 P1155 [NOIP2008 提高组] 双栈排序

    这道题哪怕是看了题解也还是不明白是怎么想到交换字母顺序卡过数据的(๑ŐдŐ)

    思路：根据输入的数据，需判断如何入栈才能保证按序输出从1~n 的值，即最小的应最先输出

    如果在一个栈中，需要满足栈中元素 i < j 且a[i] > a[j] ，如果在两个栈中，栈中的三个元素需满足 k < i < j 且a[k] >a[i] > a[j]

    那么，要如何将这些元素分配到两个栈中呢？

    设1\leqslant i < j < n。 若存在j < k \leqslant n 使得a[k] < a[i] < a[j] 则a[i],a[j]不能进入同一个栈
    如果a[i]，a[j]进入了同一个栈，且a[k] < a[i] < a[j] ，那么，出栈顺序为a[k]、a[i] 、a[j]
    a[i]先入栈，a[j]入栈使需将a[i]出栈，但a[i]应在a[k]后入栈，相互矛盾。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using namespace std;
    7. int n;
    8. const int maxn=1e6+5,INF=0x3f3f3f3f;
    9. struct node{
    10. 	int to,next;
    11. }edge[maxn<<1];
    12. int head[maxn],num=0;
    13. int a[maxn],colour[maxn],Min[maxn];
    14. bool vis[maxn];
    15. char result[maxn];
    16. inline int read()
    17. {
    18. 	int x=0,f=1;
    19. 	char c=getchar();
    20. 	while(c<'0'||c>'9')
    21. 	{
    22. 		if(c=='-') f=-1;
    23. 		c=getchar();
    24. 	}
    25. 	while(c>='0'&&c<='9')
    26. 	{
    27. 		x=(x<<3)+(x<<1)+(c^48);
    28. 		c=getchar();
    29. 	}
    30. 	return x*f;
    31. }
    32.  
    33. inline void add(int u,int v)
    34. {
    35. 	edge[++num].to=v;
    36. 	edge[num].next=head[u];
    37. 	head[u]=num;
    38. }
    39.  
    40. inline void dfs(int num,int col)
    41. {
    42. 	colour[num]=col;
    43. 	for(int i=head[num];i!=-1;i=edge[i].next)
    44. 	{
    45. 		int v=edge[i].to;
    46. 		if(!colour[v]) dfs(v,3-col);
    47. 		if(colour[v]==col) 
    48. 		{
    49. 			printf("0");
    50. 			exit(0);
    51. 		}
    52. 	}
    53. }
    54.  
    55. int main()
    56. {
    57. 	n=read();
    58. 	memset(head,-1,sizeof(head));
    59. 	memset(Min,INF,sizeof(Min));
    60. 	for(int i=1;i<=n;++i)
    61. 	{
    62. 		a[i]=read();
    63. 	}
    64. 	for(int i=n;i>=1;--i) //用于找到i,j,k三个数中的最小值（即分析中假设分成两个栈的情况）
    65. 	{
    66. 		Min[i]=min(a[i],Min[i+1]);
    67. 	}
    68. 	
    69. 	for(int i=1;i<=n-1;++i)
    70. 	{
    71. 		for(int j=i+1;j<=n;++j)
    72. 		{
    73. 			if((a[i]1]//需要将两个数放在不同的集合中
    74. 			{
    75. 				add(i,j); add(j,i); //建立二分图
    76. 			}
    77. 		}
    78. 	}
    79. 	
    80. 	for(int i=1;i<=n;++i)
    81. 	{
    82. 		if(!colour[i]) dfs(i,1);
    83. 	}
    84. 	stack <int> s1;
    85. 	stack <int> s2;
    86. 	int check=1,sum=0;
    87. 	for(int i=1;i<=n;++i)
    88. 	{
    89. 		if(colour[i]==1) //二分图左边的元素
    90. 		{
    91. 		s1.push(a[i]);
    92. 		result[++sum]='a';
    93. 		}
    94. 		else 
    95. 		{
    96. 			s2.push(a[i]);
    97. 				result[++sum]='c';
    98. 		}
    99. 		while((!s1.empty()&&s1.top()==check)||(!s2.empty()&&s2.top()==check)) 
    100.         //如果最两个栈其中一个顶端的元素是排成1~n在此次所找的数
    101. 		{
    102. 			if (!s1.empty()&&s1.top()==check) 
    103. 			{
    104. 			s1.pop();
    105. 			result[++sum]='b';
    106. 			}
    107. 			else
    108. 			{
    109. 			s2.pop();
    110. 			result[++sum]='d';
    111. 			}
    112. 			++check;
    113. 		}	
    114. 	}
    115. 	
    116. 	for(int i=sum-1;i>=1;--i) //从后往前找，缩小查找的范围
    117. 	{
    118. 		for(int j=i;j
    119. 		{
    120. 			if(result[j]=='d'&&result[j+1]=='a')
    121. 			{
    122. 				swap(result[j],result[j+1]);
    123. 			}
    124. 			else break;
    125. 		}
    126. 	}
    127. 	
    128. 	for(int i=1;i<=sum;++i)
    129. 	{
    130. 		printf("%c ",result[i]);
    131. 	}
    132. 	return 0;
    133. }


    二 . 匈牙利算法

    1 . 二分图最大匹配

    求二分图最大匹配，就是从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。

    模板题 ： 洛谷 P3386 【模板】二分图最大匹配

    题目描述

    给定一个二分图，其左部点的个数为 n，右部点的个数为 m，边数为 e，求其最大匹配的边数。

    左部点从 1 至 n 编号，右部点从 1 至 m 编号。

    输入格式

    输入的第一行是三个整数，分别代表 n，m 和 e。

    接下来 e 行，每行两个整数 u, v，表示存在一条连接左部点 u 和右部点 v 的边。

    输出格式

    输出一行一个整数，代表二分图最大匹配的边数。

    输入输出样例

    输入 #1

    1 1 1
1 1

    输出 #1

    1

    输入 #2

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

    输出 #2

    2

    说明/提示

    数据规模与约定

    对于全部的测试点，保证：

    • 1 \leqslant n, m \leqslant 500 。
    • 1 \leqslant e \leqslant 5 \times 10^4。
    • 1 \leqslant u \leqslant n,1 \leqslant v \leqslant m 。

    不保证给出的图没有重边。

  • 相关阅读:
    那些项目中遇到的注解
    性能监控的革命：Eureka引领分布式服务监控新纪元
    [RK3399] [Firefly-Ubuntu] 1min教你搭建远程桌面
    学习笔记——指针！
    【类加载子系统】
    14、三维表面重建-DeepSDF
    Testng监听器
    图扑数字孪生北京故宫，推进旅游业元宇宙进程
    HarmonyOS系统中内核实现烟雾检测的方法
    MySQL如何改进LRU算法
  • 原文地址：https://blog.csdn.net/gzkeylucky/article/details/126445672