关押罪犯

好久不做并查集了……

我们把fa[i + n]看作i的敌人的集合

↑与食物链有几分相似

把仇视关系按权值从大到小排序

一个个合并

 1     sort(edge + 1, edge + m + 1, cmp);
 2     for(int i = 1; i <= (n << 1); i++) fa[i] = i;
 3     int xx, yy;
 4     for(int i = 1; i <= m; i++){
 5         xx = edge[i].x, yy = edge[i].y;
 6         if(find(xx) == find(yy)){
 7             printf("%d", edge[i].w);
 8             return 0;
 9         }
10         else {
11             fa[find(xx)] = fa[find(yy + n)];//!!!
12             fa[find(yy)] = fa[find(xx + n)];
13         }
14     }
15     printf("0");

关键部分

注意啊！并查集之间做操作一定要用最大的祖宗做！