CQUPT 并查集

题解

uestc 1328：卿学姐与诡异村庄
题意：
中文题目。
思路：
首先，我们把好人与坏人分为两部分，好人为前n，坏人为后n，所以rank与par的数组大小均要略大于2 × n。
当t为1时，i与ai要么全为好人，要么全为坏人，所以这时我们分别合并i与ai，i+n与ai+n。
最后，要判断是否存在合理的分类，即一个人的好坏是确定的，所以只需判断i 与 i+n 是否在一个集合中，因为如果i与i+n在同一个集合中，就说明i既是好人，又是坏人，显然矛盾，这时就不存在一个明确的分类。
代码：

#include <stdio.h>
#include <string.h>
int par[200005];
int rank[200005];
int find(int x)
{
    if (par[x] == x)
        return x;
    else
        return find(par[x]);
}
void uni(int x,int y)
{
    if (rank[x] < rank[y])
    {
        par[x] = y;
    }
    else
    {
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}
int main()
{
    int n;
    while (scanf("%d",&n) == 1)
    {
        memset(par,0,sizeof(par));
        memset(rank,0,sizeof(rank));
        for (int i = 1;i <= 2*n;i++)
            par[i] = i;
        for (int i = 1;i <= n;i++)
        {
            int ai,t;
            scanf("%d%d",&ai,&t);
            if (t == 1)
            {
                uni(find(i),find(ai));
                uni(find(i+n),find(ai+n));
            }
            else
            {
                uni(find(i),find(ai+n));
                uni(find(i+n),find(ai));
            }
        }
        int flag = 1;
       // printf("%d %d\n",find(3),find(6));
        for (int i = 1;i <= n;i++)
            if (find(i) == find(i+n))
            {
                flag = 0;
                break;
            }
        if (flag) printf("Time to show my power\n");
        else printf("One face meng bi\n");
    }
    return 0;
}

poj1182:食物链（实在是经典中的经典啊
题意：
中文题目。
思路：
一开始最难想到的是如何表示a吃b，b吃c，c吃a的关系，然后由卿学姐那道题想到了用偏移量来表示这种似乎不能确定的关系，mark一下。然后呢，就是对输入数据的判断了，关键的是判断关系。这里分两种情况
1.输入x与y为同类，则判断是否已存在x与y互吃的关系，即3选1判断就行了，因为在unite的时候是把3种都进行了考虑的，所以直接两个same解决，这个具体见代码。
2.输入x吃y，则判断x与y是否同类或者是否存在y吃x就行了，用同样的方法。
××××××××××××××××××××××××××重点××××××××××××××××××××××××××××
1.路径压缩，即 return par[x] = find(par[x])
这是让我觉得很美的地方，让复杂度数量级的减小。
2.在poj的discuss上看到的极美的代码，那就是不用rank数组（要不然就要mle了），unite的时候，当两个点的根不相等的时候，直接连起来就行了，不需考虑高度，我直觉是因为有路径压缩的原因。见代码啦。
代码：

#include <stdio.h>
#include <string.h>
int par[150002];
int find(int m)
{
    if (par[m] == m)
        return m;
    else
        return par[m] = find(par[m]);
}
void uni(int m,int n)
{
    int mm = find(m);
    int nn = find(n);
    if (mm != nn) par[mm] = nn;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    memset(par,0,sizeof(par));
    for (int i = 1;i <= n * 3;i++) par[i] = i;
    int ans = 0;
    for (int i = 1;i <= k;i++)
    {
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        if (x <= 0||y <= 0 || x > n || y > n)
        {
            ans++;
            continue;
        }
        if (t == 2 && x == y)
        {
            ans++;
            continue;
        }
        int flag = 1;
        if (t == 1)
        {
            if (find(x) == find(y + n) || find(y) == find(x + n))
                flag = 0;
        }
        if (t == 2)
        {
            if (find(x) == find(y) || find(y) == find(x + n))
                flag = 0;
        }
        if (flag == 0)
        {
            ans++;
            continue;
        }
        if (t == 1)
        {
            uni(x,y);
            uni(x+ n,y+ n);
            uni(x + 2 * n,y + 2 * n);
        }
        else
        {
            uni(x,y + n);
            uni(x+n,y + 2 * n);
            uni(x + 2 * n,y);
        }
    }
    printf("%d\n",ans);
    return 0;
}

hud1213 ： HOW MANY TABLES
题意：
有n个人，已知某两个是认识的，现在要安排位置给这n个人，要求是对于某一桌子上的任意一个人，在这张桌子上必须要有他认识的人，问最少需要多少张桌子。
思路：
并查集，求一共有多少个父亲。
我的思路不是这个，是求这张图中有多少个连通图。用深度优先搜索。
代码：

#include <bits/stdc++.h>
using namespace std;
char mp[1005][1005];
int m,n;
void dfs(int x,int y)
{
    mp[x][x] = mp[y][y] = 0;
    mp[x][y] = mp[y][x] = 0;
    for (int i = 1;i <= n;i++)
    {
        if (mp[i][x] == 1) dfs(i,x);
        if (mp[i][y] == 1) dfs(i,y);
    }
    return;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int res = 0;
        memset(mp,0,sizeof(mp));
        scanf("%d%d",&n,&m);
        for (int i = 0;i < m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            mp[x][y] = mp[y][x] = 1;
        }
        for (int i = 1;i <= n;i++) mp[i][i] = 1;
        for (int i = 1;i <= n;i++)
            for (int j = i;j <= n;j++)
        {
            if (mp[i][j] == 1)
            {
                res++;
                dfs(i,j);
            }
        }
        printf("%d\n",res);
    }
    return 0;
}

poj 1962 : CORPORATIVE NETWORK
题意：
带权值并查集裸题。给出n个数，每个数的起始权值为0，然后给出一些数对，如x，y，则x的父亲是y，当且仅当y无父亲时，x的权值为|x-y|%1000；若y有父亲，则x的权值就是x一直到根的各个点的权值相加。有两种操作，一种是查询x的权值，另一种是将x连接到y上。
思路：
每次查询的时候，一路更新各个点的权值（中文表达能力太差。。。），具体看代码。
代码：

#include <stdio.h>
#include <string.h>
int par[20005];
int dist[20005];
int abs(int x)
{
    return x >= 0 ? x : (-x);
}
int find(int x)
{
    if (par[x] == x)
        return x;
    int res = find(par[x]);
    dist[x] += dist[par[x]];/*find需在累加面前是因为值在从根的点开始从后往前更新的（回溯，可以举例）*/
    par[x] = res;
    return res;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        memset(par,0,sizeof(par));
        memset(dist,0,sizeof(dist));
        for (int i = 1;i <= n;i++) par[i] = i;
        char k[10];
        while (scanf(" %s",k) != EOF)
        {
            if (k[0] == 'O') break;
            if (k[0] == 'E')
            {
                int i;
                scanf("%d",&i);
                find(i);
                printf("%d\n",dist[i]);
            }
            else
            {               
                int i,j;
                scanf("%d%d",&i,&j);
                par[i] = j;
                dist[i] = (abs(i-j)) % 1000;
            }
        }
    }
    return 0;
} 

此题的血的教训是，题上给出的字母或数字等，答案格式直接从题上复制就好了（你根本不知道题上给的到底是什么

UVA 11631：DARK ROADS
题意：
求一个图的最小生成树，然后求图的每条边的权值之和减去最小生成树的权值之和。
思路：
用一个pair来表示一条边，first是一个pair表示两个点，second表示这条边的权值。然后将边进行排序，依据权值进行。用kruskal算法对边进行选择，判断两点是否联通的时候，就用并查集。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef pair<int,int> p;
typedef pair<p,int> pp;
pp mmp[200005];
int par[200005];
int ran[200005];
bool cmp(pp &a,pp& b)
{
    return a.second < b.second;
}
int fin(int x)
{
    if (par[x] == x)
        return x;
    else
        return par[x] = fin(par[x]);
}
void unit(int x,int y)
{
    int px = fin(x);
    int py = fin(y);
    if (ran[px] < ran[py])
        par[px] = py;
    else
    {
        par[py] = px;
        if (ran[py] == ran[px]) ran[px]++;
    }
}
int main()
{
    int m,n;
    while (scanf("%d%d",&m,&n) != EOF)
    {
        if (m == 0 && n == 0) break;
        memset(mmp,0,sizeof(mmp));
        memset(par,0,sizeof(par));
        memset(ran,0,sizeof(ran));
        int sum = 0;
        for (int i = 0;i < m;i++) par[i] = i;
        for (int i = 0;i < n;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            mmp[i].first.first = x;
            mmp[i].first.second = y;
            mmp[i].second = z;
            sum += z;
        }
        sort(mmp,mmp+n,cmp);
        int ans = 0;
        int edge = 0;
        for (int i = 0;i < n;i++)
        {
            int x = mmp[i].first.first;
            int y = mmp[i].first.second;
            if (fin(x) == fin(y)) continue;
            ans += mmp[i].second;
            edge++;
            unit(x,y);
            if (edge == m - 1) break;
        }
        ans = sum - ans;
        printf("%d\n",ans);
        //printf("%d",sum);
    }
    return 0;
}

注意：这题的sort写了之后cmp之后却没有加到sort里面，下次要注意，因为这个还卡了不短的时间。