zcmu1435（帶删除并查集）

題目連結：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?id=1435

這道題目我們可以用并查集來做，隻是這道題需要我們去删除；

如果沒接觸過并查集可以先看一下并查集算法

這裡有一篇講并查集基本操作的部落格：https://blog.csdn.net/qq_38939675/article/details/79317357

接着這道題目就隻要注意怎麼去處理删除了，直接貼代碼。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int Max = 0x3f3f3f3f;
const int Min = 0xc0c0c0c0;
const int maxn = 123456;
#define mst(a) memset(a,0,sizeof(a))
int t,n,m,cnt,Case,num;
int pre[maxn],vis[maxn],real[maxn];//pre數組是用來存上級的 vis為标記數組 real為真實的位置
int find(int x)
{
    int root =x;
    while(root!=pre[root])//尋找上級
    {
        root=pre[root];
    }
    int j=x;
    while(j!=root)//路徑壓縮
    {
        int temp=pre[j];
        pre[j]=root;
        j=temp;
    }
    return root;
}
int main()
{
    while(cin>>m>>n)
    {
        if(m+n==0) return 0;
        Case=0;
        num=0;
        cnt=n;
        for(int i=0;i<m;i++)
        {
            pre[i]=i;//剛開始上級就是自己
            real[i]=i;//剛開始位置就是自己
        }
        mst(vis);
        string s;
        int a,b;
        for(int i=0; i<n; i++)
        {
            cin>>s;
            if(s[0]=='M')
            {
                cin>>a>>b;
                a=find(real[a]);
                b=find(real[b]);
                if(a!=b)//判斷上級是否一樣
                {
                    pre[a]=b;
                }
            }
            else {
                    cin>>a;
                real[a]=cnt;//更新位置
                pre[cnt]=cnt;//更新上級
                cnt++;
            }
        }
        for(int i=0;i<m;i++)
            {
                int x=find(real[i]);//尋找上級
                if(!vis[x])
                {
                    vis[x]=1;
                    num++;
                }
            }
        printf("Case #%d: %d\n", ++Case,num);
    }
    return 0;
}





           

這道題目我了解了很長的時間，主要是困在于路徑壓縮，我舉個例子吧！

比如說1和2聯盟然後2和3聯盟，按照道理此時1和3應該也是盟國，代碼可以實作這個功能，但是實際上是在最後一次周遊所有國家的時候才将1的上級改為3的，是以說這裡需要注意，我在舉個例子比如1和2聯盟然後2和3聯盟，然後1又和4聯盟，此時我們在前面比較1和4的上級是不是一樣的時候就會去更新1的上級變成3是以說會有一些國家的上級會更新但是隻是部分。