P1892 [BOI2003]团伙题解+并查集题目板子汇总

虽然题解区已经满了，但是，还是有一种并查集的方法可以拿来介绍。

首先是并查集的初始化部分，我一般喜欢单独写一个函数，当然，直接放在main里也不是不可以。

int node[10001], high[10001], isdi[10001];
//多定义一个isdi（是不是敌人）
void init(int n) {
    //用作初始化
    int i;
    for (i = 1; i <= n; i++) {
	node[i] = i;
	high[i] = 0;
    }
}

之后就是树上操作，要做的就是判断两个集合是否一致，然后进行合并（整体一笔带过，属于板子，详细请看注释）

int findgen(int i) {
    //用于寻找根节点
    if (node[i] == i) return i;
    node[i] = findgen(node[i]);
    return node[i];
    //return 0;
}
void hebing(int x, int y) {
    //用于合并两棵树
    x = findgen(x);//第1棵树的高度
    y = findgen(y);//第2棵树的高度
    if (x == y) return;
    if (high[x] > high[y]) {
	//如果第1棵树的高度高过第2棵树的高度
	node[y] = x;
    }
    else if (high[x] == high[y]) {
	node[y] = x;
	high[x]++;
    }
    else node[x] = y;
    return;
}
bool check(int x, int y) {
    bool flag = 0;
    if (findgen(x) == findgen(y)) flag = true;
    else flag = false;
    return flag;
}

最后，并查集的内容已经做完了，而剩下的需要操作的就是在main函数里判断、合并、不断重复，如下：

char y;
int p, q;
for (int i = 1; i <= m; i++) {
    cin >> y >> p >> q;
    //是朋友，还是敌人呢？
    if (y == 'F') {
      //朋友
      hebing(p, q);
    }
    else if (isdi[p] == 0) {
	isdi[p] = findgen(q);
    }
    else hebing(q, isdi[p]);//合并
    if (isdi[q] == 0) isdi[q] = findgen(p);//不断地重复
    else {
	hebing(p, isdi[q]);
    }
}

最后就是输出。

并查集题目总结：

主要就是套用大板子，然后在主函数里进行判断、合并、输出即可，或许算得上板子题？
板子可以这么套：

void init(int n) {
    //用作初始化
    int i;
    for (i = 1; i <= n; i++) {
	node[i] = i;
	high[i] = 0;
    }
}
int findgen(int i) {
    //用于寻找根节点
    if (node[i] == i) return i;
    node[i] = findgen(node[i]);
    return node[i];
    //return 0;
}
void hebing(int x, int y) {
    //用于合并两棵树
    x = findgen(x);//第1棵树的高度
    y = findgen(y);//第2棵树的高度
    if (x == y) return;
    if (high[x] > high[y]) {
	//如果第1棵树的高度高过第2棵树的高度
	node[y] = x;
    }
    else if (high[x] == high[y]) {
	node[y] = x;
	high[x]++;
    }
    else node[x] = y;
    return;
}
bool check(int x, int y) {
    bool flag = 0;
    if (findgen(x) == findgen(y)) flag = true;
    else flag = false;
    return flag;
}

这么一道绿体我居然提交了3遍才过，写一篇题解纪念一下我码码码挂挂挂的题目。

看的这么不容易，不点个赞再走嘛