哎……做了这题，我才敢说我真的会了点并查集

这是道很经典，很有意思的并查集题目

其实也不难，每个点记录敌人集合然后乱搞即可

代码：

/**************************************************************
    Problem: 1370
    User: danihao123
    Language: C++
    Result: Accepted
    Time:72 ms
    Memory:1288 kb
****************************************************************/
 
#include <iostream>
#include <set>
using namespace std;
const int maxn=1001;
int p[maxn],rank[maxn],e[maxn];
int find_set(int x){
    if(x==p[x])
        return x;
    else
        return p[x]=find_set(p[x]);
}
inline int link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
        return x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
        return y;
    }
}
int merge_set(int x,int y){
    register int set_x=find_set(x),set_y=find_set(y);
    if(set_x!=set_y)
        return link_set(set_x,set_y);
    else
        return set_x;
}
int main(){
    register int i;
    int n,m,temp,k;
    char ch;
    set<int> s;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        p[i]=i;
    for(i=1;i<=m;i++){
        cin>>ch>>temp>>k;
        if(ch=='E'){
            if(e[temp])
                e[temp]=merge_set(e[temp],k);
            else
                e[temp]=k;
            if(e[k])
                merge_set(e[k],temp);
        }else{
            merge_set(temp,k);
        }
    }
    for(i=1;i<=n;i++)
        s.insert(p[i]);
    cout<<s.size()<<endl;
    return 0;
}

• 相关文章
• 全局相关文章