蓝桥杯 并查集_蓝桥杯考并查集吗

C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。
　　如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起抗议。
　　现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。

输入格式

输入的第一行包含两个整数n, m，分别表示小岛的个数和桥的数量。
　　接下来m行，每行三个整数a, b, t，分别表示该座桥连接a号和b号两个小岛，能使用t天。小岛的编号从1开始递增。

输出格式

输出一个整数，表示居民们会抗议的天数。

样例输入

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

样例输出

2

样例说明

第一天后2和3之间的桥不能使用，不影响。
　　第二天后1和2之间，以及1和3之间的桥不能使用，居民们会抗议。
　　第三天后3和4之间的桥不能使用，居民们会抗议。

数据规模和约定

对于30%的数据，1<=n<=20，1<=m<=100；
　　对于50%的数据，1<=n<=500，1<=m<=10000；
　　对于100%的数据，1<=n<=10000，1<=m<=100000，1<=a, b<=n， 1<=t<=100000。

#include<iostream>
#include<stdio.h>
using namespace std; 


typedef int set;
typedef struct {
	int start;
	int end;
	int width;
}Map;

void init(set* s,int size){
	for(int i=0;i<size;i++)
		 s[i]=-1;
}


int find(set* s,int x){
	while(s[x]>=0)
		x=s[x];
	return x;
}


void unio(set *s,int x,int y){
	
	int a=find(s,x);
	int b=find(s,y);
	if(a!=b)
	{
			if(s[a]>=s[b]){     //按高度进行路径压缩 
			if(s[a]==s[b])
				s[b]--;
				s[a]=b;	
		}
		else{
			s[b]=a;
		}
		
	}
	
	
	
	
}


int main(){
	
	int m;
	int n;
	FILE *file=fopen("E:\\1.txt","r");
	 fscanf(file,"%d%d",&m,&n);


	
	Map* map=new Map[n]; 
	int count=0;
	for(int i=0;i<n;i++)
	{
		 fscanf(file,"%d%d%d",&map[i].start,&map[i].end,&map[i].width);
		 count=count>map[i].width?count:map[i].width;
	}

	set* s=new int[m+1];

	


	
	int circle=0;
	int pre=0;
	int result=0;
 
	
for(int i=0;i<count+1;i++){
		init(s,m+1);
		for(int j=0;j<n;j++){
			if(map[j].width>0)
				{
					unio(s,map[j].start,map[j].end);   //放入一个集合 
					map[j].width--;
				}
		
		}
	
		int k=0;  //统计当前的连通分量 
		for(int i=1;i<m+1;i++)
		if(s[i]<0){
			
				k++;
			}
		
				if(k>pre)
			{
			pre=k;
			result++;
			}	
		}
	
		
	cout<<result-1;
		

	
	
	
	
	


	
	
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116