• 学习笔记——并查集

    并查集的作用：解决连通性问题（连通性问题：对于集合中的点，进行连通以及查询的过程）

    Quick-Find算法

    基于染色的思想，处于相同连通集合的点，染成相同的颜色。

    合并操作：时间复杂度O(n)，将一个连通子集中的点的染色全部染成另一个连通子集的颜色。

    查询操作：时间复杂度O(1)，只需要判断该点的颜色。

    由于合并操作时间复杂度较高，故Quick-Find算法并不作为常用的并查集算法。

    代码实现

    1. #include
    2. using namespace std;
    3. #define MAX_N 100
    4. int arr[MAX_N+5];
    5. void Init(int n)
    6. {
    7. 	for(int i=0;i
    8. 	arr[i]=i;//每个点的颜色初始化为序号 
    9. 	return ;
    10. }
    11. void output(int *arr,int n)
    12. {
    13. 	int ret=0;
    14. 	for(int i=0;i
    15. 	ret+=printf("%3d",i);
    16. 	printf("\n");
    17. 	for(int i=0;i<=ret+1;i++)
    18. 	printf("-");
    19. 	printf("\n");
    20. 	for(int i=0;i
    21. 	printf("%3d",arr[i]);
    22. 	printf("\n");
    23. 	return ;
    24. }
    25. int find(int i)
    26. {
    27. 	return arr[i];//直接返回颜色 
    28. }
    29. int merge(int a,int b,int n)
    30. {
    31. 	int aa=find(a),bb=find(b);
    32. 	if(aa==bb)return 0;//如果两个点在一个集合，直接返回 
    33. 	for(int i=0;i//找到所有原先和a颜色一样的点 
    34. 	{
    35. 		if(find(i)==aa)
    36. 		arr[i]=bb;//颜色更新为b的颜色 
    37. 	}
    38. 	return 1;
    39. }
    40. int main()
    41. {
    42. 	int n;
    43. 	cin>>n;
    44. 	Init(n);
    45. 	output(arr,n);
    46. 	int a,b;
    47. 	while(cin>>a>>b)
    48. 	{
    49. 		printf("merge %d with %d:%d\n",a,b,merge(a,b,n));
    50. 		output(arr,n);
    51. 	}
    52. 	return 0;
    53.  }

    Quick-Union算法

    解决了Quick-Find算法合并太慢的问题，使用树形结构父子节点之间的关系来说明是否在一个集合，即Union在同一集合的两个点有相同的根节点。

    合并操作：将一棵树作为另一棵树的子树（时间复杂度取决于树高）

    查询操作：递归查找到该节点所在树的根节点（时间复杂度取决于树高）

    代码实现

    1. #include
    2. using namespace std;
    3. #define MAXSIZE 100
    4. int fa[MAXSIZE+5];
    5. void Init(int n)
    6. {
    7. 	for(int i=0;i
    8. 	{
    9. 		fa[i]=i;//每个节点的父节点初始化为序号 
    10. 	}
    11. 	return ;
    12. }
    13. void output(int *arr,int n)
    14. {
    15. 	int ret=0;
    16. 	for(int i=0;i
    17. 	ret+=printf("%3d",i);
    18. 	printf("\n");
    19. 	for(int i=0;i<=ret+1;i++)
    20. 	printf("-");
    21. 	printf("\n");
    22. 	for(int i=0;i
    23. 	printf("%3d",arr[i]);
    24. 	printf("\n");
    25. 	return ;
    26. }
    27. int find(int a)
    28. {
    29. 	if(fa[a]==a)return a;
    30. 	//当前点是根节点，直接返回 
    31. 	return find(fa[a]);//若不是根节点则递归找到根节点 
    32. }
    33. int merge(int a,int b)
    34. {
    35. 	if(find(a)==find(b))return 0;
    36. 	//有同一个根节点，说明在同一个连通子集 
    37. 	fa[find(a)]=find(b);
    38. 	//将a的根节点连在b的根节点上 
    39. 	return 1;
    40. }
    41. int main()
    42. {
    43. 	int n;
    44. 	cin>>n;
    45. 	Init(n);
    46. 	output(fa,n);
    47. 	int a,b;
    48. 	while(cin>>a>>b)
    49. 	{
    50. 		printf("merge %d with %d:%d\n",a,b,merge(a,b));
    51. 		output(fa,n);
    52. 	}
    53. 	return 0;
    54.  }

    Quick-Union算法存在的问题：极端情况下会形成链表，使得find操作的效率大大降低，因此需要对Quick-Union进行优化。

    Quick-Union的优化

    按秩优化

    在普通的Quick-Union实现中，find算法的实现总是将a的根节点连接在b的根节点上，这可能会导致树的退化，例如形成链表，因此在每次连接之前，可以以树的高度为参考依据将高度较矮的树连在高度较高的树下面，或者将节点数较少的树连在节点数较多的树下面。

    代码实现

    1. #include
    2. using namespace std;
    3. #define MAXSIZE 100
    4. int fa[MAXSIZE+5];
    5. int size[MAXSIZE+5]; 
    6. void Init(int n)
    7. {
    8. 	for(int i=0;i
    9. 	{
    10. 		fa[i]=i;//每个节点的父节点初始化为序号 
    11. 		size[i]=1;//以每个点以根节点的树的大小 
    12. 	}
    13. 	return ;
    14. }
    15. void output(int *arr,int n)
    16. {
    17. 	int ret=0;
    18. 	for(int i=0;i
    19. 	ret+=printf("%3d",i);
    20. 	printf("\n");
    21. 	for(int i=0;i<=ret+1;i++)
    22. 	printf("-");
    23. 	printf("\n");
    24. 	for(int i=0;i
    25. 	{
    26. 		printf("%3d",arr[i]);		
    27. 	}
    28. 	printf("\n");
    29. 	for(int i=0;i
    30. 	{
    31. 		printf("%3d",size[i]);		
    32. 	}
    33. 	printf("\n");
    34. 	return ;
    35. }
    36. int find(int a)
    37. {
    38. 	if(fa[a]==a)return a;
    39. 	//当前点是根节点，直接返回 
    40. 	return find(fa[a]);//若不是根节点则递归找到根节点 
    41. }
    42. int merge(int a,int b)
    43. {
    44. 	int aa=find(a),bb=find(b);
    45. 	if(aa==bb)return 0;
    46. 	//有同一个根节点，说明在同一个连通子集 
    47. 	if(size[aa]
    48. 	{
    49. 		fa[aa]=bb;
    50. 		size[bb]+=size[aa];
    51. 		//将a的根节点连在b的根节点上 
    52. 	}
    53. 	else {
    54. 		fa[bb]=aa;
    55. 		size[aa]+=size[bb];
    56. 	}
    57. 	return 1;
    58. }
    59. int main()
    60. {
    61. 	int n;
    62. 	cin>>n;
    63. 	Init(n);
    64. 	output(fa,n);
    65. 	int a,b;
    66. 	while(cin>>a>>b)
    67. 	{
    68. 		printf("merge %d with %d:%d\n",a,b,merge(a,b));
    69. 		output(fa,n);
    70. 	}
    71. 	return 0;
    72.  }

    路径压缩

    背景：因为Quick-Union操作的时间消耗取决于树高，为了降低每次find的消耗，我们要尽可能让树形结构变扁，但是如果我们每次在merge操作的时候去把一棵树上的各点都连接到另一棵树时，这会导致Quick-Union算法退化为Quick-Find算法，即merge的时间复杂度变成O(n)。

    在每次find而不是merge的时候将当前结点以及当前点之前路径上的所有点挂在根节点上，可以减少很多的无用合并，达到均摊时间度为O(1)的效果。

    代码实现

    1. #include
    2. using namespace std;
    3. #define MAXSIZE 100
    4. int fa[MAXSIZE+5];
    5. void Init(int n)
    6. {
    7. 	for(int i=0;i
    8. 	{
    9. 		fa[i]=i;//每个节点的父节点初始化为序号 
    10. 	}
    11. 	return ;
    12. }
    13. void output(int *arr,int n)
    14. {
    15. 	int ret=0;
    16. 	for(int i=0;i
    17. 	ret+=printf("%3d",i);
    18. 	printf("\n");
    19. 	for(int i=0;i<=ret+1;i++)
    20. 	printf("-");
    21. 	printf("\n");
    22. 	for(int i=0;i
    23. 	printf("%3d",arr[i]);
    24. 	printf("\n");
    25. 	return ;
    26. }
    27. int find(int a)
    28. { 
    29. 	return fa[a]=(fa[a]==a?a:find(fa[a]));
    30. 	//路径压缩 
    31. }
    32. int merge(int a,int b)
    33. {
    34. 	if(find(a)==find(b))return 0;
    35. 	//有同一个根节点，说明在同一个连通子集 
    36. 	fa[find(a)]=find(b);
    37. 	//将a的根节点连在b的根节点上 
    38. 	return 1;
    39. }
    40. int main()
    41. {
    42. 	int n;
    43. 	cin>>n;
    44. 	Init(n);
    45. 	output(fa,n);
    46. 	int a,b;
    47. 	while(cin>>a>>b)
    48. 	{
    49. 		printf("merge %d with %d:%d\n",a,b,merge(a,b));
    50. 		output(fa,n);
    51. 	}
    52. 	return 0;
    53.  }

    在实际的工作中，我们更常使用路径压缩的Quick-Union。

    例题

    1.最长连续序列

    给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

    请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

    示例 1：

    输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

    示例 2：

    输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

    思路：从前往后遍历，将值相差为1的点进行连通，最后找到size最大的连通集。

    代码实现

    1. class Quick_Union{
    2.     public:
    3.     Quick_Union(int n):fa(n+1),size(n+1)
    4.     {
    5.         for(int i=0;i<=n;i++)
    6.         {
    7.             fa[i]=i;
    8.             size[i]=1;
    9.         }
    10.     }
    11.     int find(int a)
    12.     {
    13.         return fa[a]=(fa[a]==a?a:find(fa[a]));
    14.     }
    15.     int merge(int a,int b)
    16.     {
    17.         int aa=find(a),bb=find(b);
    18.         if(aa==bb)return 0;
    19.         fa[aa]=bb;
    20.         size[bb]+=size[aa];
    21.         return 1;
    22.     }
    23.     vector<int>fa,size;
    24. };
    25. class Solution {
    26. public:
    27.     int longestConsecutive(vector<int>& nums) {
    28.         unordered_map<int,int>h;
    29.         //使用哈希表来维护值与下标之间的映射
    30.         int n=nums.size();
    31.         Quick_Union u(n);
    32.         int cnt=0;
    33.         for(int i=0;i
    34.         {
    35.            if(h.find(nums[i])!=h.end())continue;
    36.            //删除重复出现的元素
    37.            h[nums[i]]=cnt++;//下标初始化
    38.            if(h.find(nums[i]-1)!=h.end())u.merge(h[nums[i]],h[nums[i]-1]);
    39.            if(h.find(nums[i]+1)!=h.end())u.merge(h[nums[i]],h[nums[i]+1]);
    40.            //合并值连续的点
    41.         }
    42.         int ans=0;
    43.         for(int i=0;i
    44.         ans=max(ans,u.size[i]);
    45.         return ans;
    46.     }
    47. };

    使用哈希表的作用：1.进行值与下标的映射 2.将向前查找的时间复杂度由O(n)降为O(1)。

    2.被围绕的岛屿

    给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

    示例 1：

    输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

    示例 2：

    输入：board = [["X"]]
输出：[["X"]]

    思路：边上的O一定不被围绕，故除了边上的O以及与他们连通的其他O之外的O都是被围绕的。

    代码实现

    1. class Quick_Union{
    2.     public:
    3.     Quick_Union(int n):fa(n+1)
    4.     {
    5.         for(int i=0;i<=n;i++)
    6.         {
    7.             fa[i]=i;
    8.         }
    9.     }
    10.     int find(int a)
    11.     {
    12.         return fa[a]=(fa[a]==a?a:find(fa[a]));
    13.     }
    14.     int merge(int a,int b)
    15.     {
    16.         int aa=find(a),bb=find(b);
    17.         if(aa==bb)return 0;
    18.         fa[aa]=bb;
    19.         return 1;
    20.     }
    21.     vector<int>fa;
    22. };
    23. class Solution {
    24. public:
    25.     void solve(vectorchar>>& board) {
    26.         int m=board.size(),n=board[0].size();
    27.         Quick_Union u(m*n);
    28.         for(int i=0;i
    29.         {
    30.             for(int j=0;j
    31.             {
    32.                 int ind=i*n+j+1;
    33.                 if(board[i][j]=='X')continue;
    34.                 //保证只有O进行以下的判断
    35.                 if(i==0||i==m-1)u.merge(ind,0);
    36.                 if(j==0||j==n-1)u.merge(ind,0);
    37.                 //如果在边界上则与0位置连通
    38.                 if(i>0&&board[i-1][j]=='O')u.merge(ind,ind-n);
    39.                 if(j>0&&board[i][j-1]=='O')u.merge(ind,ind-1);
    40.                 //与左和上的O进行连通
    41.             }
    42.         }
    43.         for(int i=0;i
    44.         {
    45.             for(int j=0;j
    46.             {
    47.                 if(board[i][j]=='O'&&u.find(i*n+j+1)!=u.find(0))//注意是find(0),不是0
    48.                 board[i][j]='X';
    49.             }
    50.         }
    51.         return ;
    52.     }
    53. };

    3.岛屿数量

    给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

    岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

    此外，你可以假设该网格的四条边均被水包围。

    思路：记录1所组成连通子集的数量。

    示例 1：

    输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

    示例 2：

    输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

    代码实现

    1. class Quick_Union{
    2.     public:
    3.     Quick_Union(int n):fa(n)
    4.     {
    5.         for(int i=0;i
    6.         fa[i]=i;
    7.     }
    8.     int find(int a)
    9.     {
    10.         return fa[a]=(fa[a]==a?a:find(fa[a]));
    11.     }
    12.     void merge(int a,int b)
    13.     {
    14.         if(find(a)==find(b))return ;
    15.         fa[find(a)]=find(b);
    16.         return ;
    17.     }
    18.     vector<int>fa;
    19. };
    20. class Solution {
    21. public:
    22.     int numIslands(vectorchar>>& grid) {
    23.         int m=grid.size(),n=grid[0].size();
    24.         Quick_Union u(m*n);
    25.         for(int i=0;i
    26.         {
    27.             for(int j=0;j
    28.             {
    29.                 int ind=i*n+j;
    30.                 if(grid[i][j]=='0')continue;
    31.                 if(i>0&&grid[i-1][j]=='1')u.merge(ind,ind-n);
    32.                 if(j>0&&grid[i][j-1]=='1')u.merge(ind,ind-1);
    33.             }
    34.         }
    35.         int ans=0;
    36.         for(int i=0;i
    37.         {
    38.             for(int j=0;j
    39.             {
    40.                 int ind=i*n+j;
    41.                 if(grid[i][j]=='0')continue;
    42.                 if(u.fa[ind]==ind)ans+=1;
    43.             }
    44.         }
    45.         return ans;
    46.     }
    47. };

     4.省份数量

    有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

    省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

    给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

    返回矩阵中 省份 的数量。

    示例 1：

    输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

    示例 2：

    输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

    代码实现

    1. class UnionSet{
    2.     public:
    3.     UnionSet(int n):fa(n+1){
    4.         for(int i=0;i<=n;i++)
    5.         fa[i]=i;
    6.     }
    7.     int get(int k)
    8.     {
    9.         return fa[k]=(fa[k]==k?k:get(fa[k]));
    10.     }
    11.     void merge(int a,int b)
    12.     {
    13.         fa[get(a)]=fa[get(b)];
    14.         return ;
    15.     }
    16.     vector<int>fa;
    17. };
    18. class Solution {
    19. public:
    20.     int findCircleNum(vectorint>>& isConnected) {
    21.         int n=isConnected.size();
    22.         UnionSet u(n);
    23.         for(int i=0;i
    24.         {
    25.             for(int j=i+1;j
    26.             {
    27.                 if(isConnected[i][j]==1)u.merge(i,j);
    28.             }
    29.         }
    30.         int ans=0;
    31.         for(int i=0;i
    32.         if(u.fa[i]==i)ans+=1;
    33.         return ans;
    34.     }
    35. };

    5.猜拳 

    题目描述

    ​ 在一次聚会中，每人拿着一张印有石头、剪刀、布的卡片，每个人具体拿得是哪种卡片不得而知。

    ​ 现在告诉你某些人之间的胜负关系，并会询问某两个人之间的对战结果，人按照从 1 到 n 编号。

    ​ 对于每个询问，请给出正确的回答： Win(胜)、Loss(负)、Tie(平)

    输入

    第一行输入两个整数 n,m(1≤n≤10000，3≤m≤10000)，分别代表人数和信息数量。

    接下来 m 行，每行三个整 a,b,c（a∈[1,2], 1≤b,c≤n）

    1. 当 a=1 时，代表新增一条已知信息，表示 b, c 对战中 b 胜
    2. 当 a=2 时，代表根据以上信息，询问 b,c 对战中 b​ 的结果

    如果出现某条新增的信息与之前的信息发生冲突，就忽略此条信息。

    输出

    对于每个 a=2 的操作，输出 Win、Loss、Tie 或 Unknown 代表对战双方的结果。

    样例输入

    1. 6 6
    2. 1 1 2
    3. 2 1 3
    4. 1 2 4
    5. 1 4 3
    6. 2 1 3
    7. 2 4 1

    样例输出

    1. Unknown
    2. Tie
    3. Win

    思路：如果题目只问两个人之间的输赢关系能否判断的话，那么只用普通的并查集就能解决该问题，即在一个连通集中的人能够判断输赢关系，但是题目中进一步问了两个人之间的输赢关系是什么，那么就需要使用带权并查集来维护这个关系。

    在对xw和yz进行merge操作时需要知道c的值，c=(t+b-a+3)%3。

    代码实现

    1. #include
    2. #include
    3. using namespace std;
    4. class UnionSet
    5. {
    6. 	public:
    7. 		UnionSet(int n):fa(n+1),val(n+1)
    8. 		{
    9. 			for(int i=0;i
    10. 			{
    11. 				fa[i]=i;
    12. 				val[i]=0;
    13. 				//与父节点之间的路径权值，由于父节点初始化为自己，所以该值是0 
    14. 			}
    15. 		}
    16. 		int find(int a)
    17. 		{
    18. 			if(fa[a]==a)return a;
    19. 			int root=find(fa[a]);
    20. 			//将其父节点及之前的点都进行压缩，同时返回根节点 
    21. 			val[a]=(val[a]+val[fa[a]]+3)%3; 
    22. 			return fa[a]=root;
    23. 		}
    24. 		void merge(int a,int b,int t)
    25. 		{
    26. 			int aa=find(a),bb=find(b);
    27. 			if(aa==bb)return ;
    28. 			val[aa]=(t+val[b]-val[a]+3)%3;
    29. 			fa[aa]=bb;
    30. 		}
    31. 		vector<int>fa,val;
    32. };
    33. int main()
    34. {
    35. 	int n,m;
    36. 	cin>>n>>m;
    37. 	UnionSet u(n);
    38. 	for(int i=1,a,b,c;i<=m;i++)
    39. 	{
    40. 		cin>>a>>b>>c;
    41. 		if(a==1)
    42. 		{
    43. 			u.merge(b,c,1);
    44. 		}
    45. 		else
    46. 		{
    47. 			if(u.find(b)!=u.find(c))
    48. 			{
    49. 				cout<<"Unknown"<
    50. 			}
    51. 			else 
    52. 			switch((u.val[b]-u.val[c]+3)%3)
    53. 			{
    54. 				case 0:{
    55. 					cout<<"Tie"<
    56. 					break;
    57. 				}
    58. 				case 1:{
    59. 					cout<<"Win"<
    60. 					break;
    61. 				}
    62. 				case 2:{
    63. 					cout<<"Loss"<
    64. 					break;
    65. 				}
    66. 			}
    67. 			
    68. 		}
    69. 	}
    70. 	return 0;
    71.  }

    6. 程序自动分析

    题目描述

    ​ 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

    ​ 考虑一个约束满足问题的简化版本：假设 x1,x2,x3,… 代表程序中出现的变量，给定n个形如xi=xj或xi≠xj 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。

    ​ 例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

    ​ 现在给出一些约束满足问题，请分别对它们进行判定。

    输入

    ​ 输入文件的第1行包含1个正整数t，表示需要判定的问题个数。注意这些问题之间是相互独立的。

    ​ 对于每个问题，包含若干行：

    ​ 第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。

    ​ 接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若e=0，则该约束条件为xi≠xj。

    输出

    ​ 输出文件包括t行。

    ​ 输出文件的第1行输出一个字符串“YES”或者“NO”（不包含引号，字母全部大写），“YES”表示当前问题判定为可以被满足，“NO”表示不可被满足。

    输入样例1

    1. 2
    2. 2
    3. 1 2 1
    4. 1 2 0
    5. 2
    6. 1 2 1
    7. 2 1 1

    输出样例1

    1. NO
    2. YES

    思路：利用并查集去维护元素之间的相等关系，先进行相等关系的判断，若两个元素具有相等关系，则加到一个并查集里，再进行不等关系的判断，若两个元素不等，则他们先前不能在一个连通集里。

    代码实现

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. class UnionSet{
    6. 	public:
    7. 		UnionSet(int n):fa(n+1)
    8. 		{
    9. 			for(int i=0;i
    10. 			fa[i]=i;
    11. 		}
    12. 		int find(int a)
    13. 		{
    14. 			return fa[a]=(fa[a]==a?a:find(fa[a]));
    15. 		}
    16. 		void merge(int a,int b)
    17. 		{
    18. 			fa[find(a)]=find(b);
    19. 			return ;
    20. 		}
    21. 		vector<int>fa;
    22. };
    23. struct Data{
    24. 	int i,j,e;
    25. };
    26. vector<int>arr;
    27. int main()
    28. {
    29. 	int t,n;
    30. 	cin>>t;
    31. 	while(t--)
    32. 	{
    33. 		cin>>n;
    34. 		UnionSet u(2*n);
    35. 		Data d;
    36. 		vectorarr(n);
    37. 		unordered_map<int,int>h;
    38. 		int cnt=0;
    39. 		for(int k=0,i,j,e;k
    40. 		{
    41. 			cin>>i>>j>>e;
    42. 			if(h.find(i)==h.end())
    43. 			h[i]=cnt++;
    44. 			if(h.find(j)==h.end())
    45. 			h[j]=cnt++;
    46. 			d.i=h[i],d.j=h[j],d.e=e;
    47. 			arr[k]=d;
    48. 		}
    49. 		for(int i=0;i
    50. 		{
    51. 			if(arr[i].e==0)continue;
    52. 			u.merge(arr[i].i,arr[i].j);
    53. 		}
    54. 		int flag=1;
    55. 		for(int i=0;i
    56. 		{
    57. 			if(arr[i].e==1)continue;
    58. 			if(u.find(arr[i].i)==u.find(arr[i].j))
    59. 			{
    60. 				flag=0;
    61. 				break;
    62. 			}
    63. 		}
    64. 		if(flag==1)cout<<"YES"<
    65. 		else cout<<"NO"<
    66. 	}
    67. 	return 0;
    68.  }

    7.关押罪犯

    题目描述

    ​ S 城现有两座监狱，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。

    ​ 每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

    ​ 在详细考察了N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

    输入

    ​ 第一行为两个正整数N(N≤20000) 和M(M≤100000)，分别表示罪犯的数目以及存在仇恨的罪犯对数。

    ​ 接下来的M 行每行为三个正整数aj，bj，cj，表示aj 号和bj 号罪犯之间存在仇恨，其怨气值为cj。数据保证1≤aj

    输出

    输出共1行，为Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。

    输入样例1

    1. 4 6
    2. 1 4 2534
    3. 2 3 3512
    4. 1 2 28351
    5. 1 3 6618
    6. 2 4 1805
    7. 3 4 12884

    输出样例1

    3512

    思路：依然是使用带权并查集去维护两个罪犯之间是否在同一监狱的关系，根据冲突值的从大到小顺序依次判断，第一组不符合的冲突值即为答案。

    代码实现

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. class UnionSet{
    6. 	public:
    7. 		UnionSet(int n):fa(n+1),val(n+1)
    8. 		{
    9. 			for(int i=0;i<=n;i++)
    10. 			{
    11. 				fa[i]=i;
    12. 				val[i]=0;
    13. 			}
    14. 		}
    15. 		int find(int a)
    16. 		{
    17. 			if(fa[a]==a)return a;
    18. 			int root=find(fa[a]);
    19. 			val[a]=(val[a]+val[fa[a]]+2)%2;
    20. 			return fa[a]=root;
    21. 		}
    22. 		void merge(int a,int b,int t)
    23. 		{
    24. 			int aa=find(a),bb=find(b);
    25. 			if(aa==bb)return ;
    26. 			val[aa]=(t+val[b]-val[a]+2)%2;
    27. 			fa[aa]=bb;
    28. 			return ;
    29. 		}
    30. 		vector<int>fa,val;
    31. };
    32. struct Data{
    33. 	int a,b,c;
    34. };
    35. bool cmp(const Data&a,const Data&b)
    36. {
    37. 	return a.c>b.c;
    38. }
    39. int main()
    40. {
    41. 	int n,m;
    42. 	cin>>n>>m;
    43. 	vectorarr(m);
    44. 	UnionSet u(n);
    45. 	for(int i=0;i
    46. 	{
    47. 		cin>>arr[i].a>>arr[i].b>>arr[i].c;
    48. 	}
    49. 	sort(arr.begin(),arr.end(),cmp);
    50. 	int ans=0;
    51. 	for(int i=0;i
    52. 	{
    53. 		if(u.find(arr[i].a)!=u.find(arr[i].b))
    54. 		u.merge(arr[i].a,arr[i].b,1);
    55. 		else
    56. 		{
    57. 			if((u.val[arr[i].a]+u.val[arr[i].b])%2==0)
    58. 			{
    59. 			ans=arr[i].c;
    60. 			break;
    61. 			}
    62. 		}
    63. 	}
    64. 	cout<
    65. 	return 0;
    66. }

     

  • 相关阅读:
    【C++】特殊类的设计
    特征工程设计思路
    年已过半，年终立的Flag实现了几个？
    【Python】FastAPI 项目创建 与 Docker 部署
    vue中计算属性是否可以 异步获取？
    layui实现鼠标移入/移出时显示/隐藏tips
    Python深拷贝(deepcopy)、浅拷贝（copy）、等号拷贝的深入理解----看了还不懂找我
    （附源码）spring boot教学管理平台 毕业设计 281454
    java源码系列：HashMap源码验证，自己手写一个HashMap之02-写put方法以及思路、哈希冲突等
    小笔记：02-jquery-将url作为参数传递给后端，需要进行的特殊处理
  • 原文地址：https://blog.csdn.net/m0_70897036/article/details/136184209