关于并查集、矛盾关系的问题有一种经典的思路：敌人的敌人是我的朋友。
如果说的抽象一点：若存在两个矛盾关系$(a,b) (b,c)$，则$a,c$属于同一集合。后文用形象的“敌人”描述这种关系。
在具体实现时，会用一个数组记录每个人的敌人。当遇到敌人时：
①如果我有敌人，就把这两个我的敌人变成朋友。
②如果我没有敌人，他就是我的敌人。
在安排监狱时，尽可能先让冲突严重的罪犯分开。也就是先排序再处理。
其他情况就很简单了。如果我和我的敌人已经是朋友了，那就会发生冲突。直接输出就行了。
#include<iostream> #include<algorithm> #include<vector> using namespace std; int n,m,u,v; struct edge { int a,b,c; }g[100005]; int f[20005],enemy[20005]; bool operator < (edge e1,edge e2) { return e1.c>e2.c; } inline int find(int x) { if(f[x]==x) return x; return f[x]=find(f[x]); }//并查集 int main() { cin>>n>>m; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) cin>>g[i].a>>g[i].b>>g[i].c; sort(g+1,g+1+m);//排序 for(int i=1;i<=m;i++) { u=g[i].a,v=g[i].b; if(find(u)==find(v))//发生冲突 { cout<<g[i].c; return 0; } else//处理敌人 { if(!enemy[u]) enemy[u]=v; else f[find(enemy[u])]=find(v); if(!enemy[v]) enemy[v]=u; else f[find(enemy[v])]=find(u); } } cout<<0; return 0; }
原文：https://www.cnblogs.com/ehznehc/p/10555820.html