并查集&拓扑排序

1.合并两个集合

2.查询一个点所在的集合

每个集合都是一棵数，代表点是根节点

合并：将一根的父亲设为另一个根

查询：找到所在树的根

优化：

路径压缩：查询根的时候将路径上所有点的父亲设为根

按秩合并：将高度低集合向高度高集合合并

不加优化：O（n）

路径压缩/按秩合并:O（logn）

路径压缩+按秩合并:O（a(n)）

找父亲函数：

int find(int x){
    return x==fa[x]?x:find(fa[x]);
}

合并函数：

void hb(int a,int b){
    int u=find(a),v=find(b);
    if(u == v) return;
    fa[u] = v;
}

例题：关押罪犯

题目描述

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

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

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

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数 N,M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 MMM 行每行为三个正整数 aj,bj,cj，表示 aj? 号和 bj? 号罪犯之间存在仇恨，其怨气值为 cj?。数据保证 1010^9，且每对罪犯组合只出现一次。
输出格式

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

code：

#include
#define FOR(i,a,b) for(int i = (a);i <= (b);i++)
typedef long long ll;
using namespace std;
const int N = 20000+10,M = 200010;
int fa[N];
int f[M];
int n,m,ans,cnt;
struct node{
    int a,b,c;
}p[M];
bool cmp(node x,node y){
    return x.c > y.c;
}
int find(int x){
    return x==fa[x]?x:find(fa[x]);
}
int main(){
    cin>>n>>m;
    FOR(i,1,m){
        scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
    }
    FOR(i,1,n) fa[i] = i;
    sort(p+1,p+m+1,cmp);
    FOR(i,1,m){
        int u = find(p[i].a),v = find(p[i].b);
        if(u == v) return cout<0;
        if(!f[p[i].a]) f[p[i].a] = p[i].b;
        else fa[find(f[p[i].a])] = find(p[i].b);
        if(!f[p[i].b]) f[p[i].b] = p[i].a;
        else fa[find(f[p[i].b])] = find(p[i].a);
    }
    return cout<<0,0;
}

一个点能加入序列条件：当且仅当所有能到达该点的点均已加入序列（入度为0）

队列维护所有入度为0的点，

加入序列后：将与其相邻的点入度-1

将出现新的入度为0的点加入队列。