int f[100];//存储父节点 voidini()//初始化 { for (int i = 1; i <= 100; i++) f[i] = i;//一开始节点i根节点当然是i啦 } intfind(int i) { if (i == f[i])//如果i的父节点使它本身,说明到头了,i就是根节点 return i; returnfind(f[i]);//没到头就继续往下找 } voidmerge(int i, int j) { f[find(i)] = find(j);/*合并直接让一个集合的根节点连向另一个根节点就行,毕竟 根节点就是一个集合的标志*/ } boolquery(int i, int j)//查找其根节点是否一致即可 { returnfind(i) == find(j); }
#include<iostream> #include<vector> #include<algorithm> usingnamespace std; int n, m; int f[1001];//并查集数组 structE{ int x, y, t;//道路两端节点编号和时间 }edge[100001]; intfind(int x) { if (x == f[x])return x; return f[x] = find(f[x]); } intmain() { ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++)//初始化并查集 f[i] = i; for (int i = 1; i <= m; i++) cin >> edge[i].x >> edge[i].y >> edge[i].t; sort(edge + 1, edge + m + 1, [](E&l, E&r)//排序 { return l.t < r.t; }); int ans = -1;//初始化为-1,答案未更新即联不通,到时直接输出 for (int i = 1; i <= m; i++)//从早到晚枚举 { E now = edge[i]; int x = find(now.x), y = find(now.y); if (x != y)//若根节点不同 { f[x] = y;//合并 n--;//联通块数减一(刚开始n个节点独立,联通块数为1) } if (n == 1)//如果只剩一个联通块(图已联通) { ans = now.t;//答案更新 break; } } cout << ans;//直接输出 return0; }
#include<iostream> #include<vector> #include<climits> #include<string> #include<queue> #include<functional> #include<set> #include<algorithm> #include<cmath> #include<iomanip> usingnamespace std; constint MAX = 400001; int n, m; int f[MAX];//并查集 vector<int> node[MAX];//图 bool broken[MAX];//标记是否被损坏 int point[MAX];//记录损坏点 intfind(int x) { return (f[x] == x) ? x : (f[x] = find(f[x])); } intmain() { ios::sync_with_stdio(false); int n, m; cin >> n >> m; for (int i = 0; i < n; i++)//初始化 f[i] = i; for (int i = 0; i < m; i++)//建图 { int x, y; cin >> x >> y; node[x].push_back(y); node[y].push_back(x); } int k; cin >> k;//k次损坏 for (int i = 0; i < k; i++)//记录损坏的点 { int x; cin >> x; broken[x] = true; point[i] = x; } int ans = n - k;//一开始点独立,反叛军有n-k个占领点(从后往前) for (int i = 0; i < n; i++) { if (!broken[i]) { for(auto e:no/de[i])
if (!broken[e]&&find(e)!=find(i))/*如果是叛军掌握的两 个点并且还没合并*/ { ans--;//联通块数减一 f[find(i)] = find(e);//合并 } } } point[k] = ans;//point数组的损坏点逆序使用,所以用过后可以用来记录答案 for (int i = k - 1; i >= 0; i--)//从k-1到0共k个点 { int now = point[i];//弹出 broken[now] = false;//标记为未损坏 ans++;//联通块加一(有一个点进来了) for (auto e : node[now])//枚举该点所有连边 { if (!broken[e]&&find(now)!=find(e))/*如果有点与他相连且没 坏且还未合并*/ { f[find(now)] = find(e);//合并 ans--;//联通块数减一 } } point[i] = ans;//逆序记录答案
} for (int i = 0; i <= k; i++)//输出 cout << point[i] << endl; return0; }
#include<iostream> #include<vector> #include<algorithm> usingnamespace std; constint MAX = 20001; int n, m; int f[MAX * 2];//开二被数组 structrel { int x, y, val;//关系集,罪犯x和y有val的怨气 }edge[100001]; intfind(int x) { return f[x] == x ? x : (f[x] = find(f[x])); } intmain() { ios::sync_with_stdio(false); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) cin >> edge[i].x >> edge[i].y >> edge[i].val; for (int i = 1; i <= n * 2; i++)//初始化 f[i] = i; sort(edge + 1, edge + 1 + m, [](rel&l, rel&r)//排序 { return l.val > r.val; }); for (int i = 1; i <= m; i++) { int x = edge[i].x, y = edge[i].y; if (find(x)==find(y)||find(x+n)==find(y+n))//如果在同一监狱就直接输出 {//并推出main cout << edge[i].val; return0; } f[find(x + n)] = find(y);//否则就建立关系 f[find(y + n)] = find(x); } cout << 0;//如果和平解决就输出0 return0; }