进阶实验6-3.1 红色警报 (25分)--并查集

 

 解题思路：采用并查集思想

判断连通分量个数，当攻占一座城市后，图的连通分量变多，则表明影响图的连通性

#include <stdio.h>
#include <string.h>
int f[500];
int getf(int x) {
    if(f[x]==x)
        return x;
    return f[x]=getf(f[x]);
}
void merge(int x,int y) {
    int f1=getf(x);
    int f2=getf(y);
    f[f1]=f2;
}
void Init(int f[],int n) {//初始化并查集集合
    int i;
    for(i=0; i<n; i++) {
        f[i]=i;
    }
}
int Cnt(int f[],int n) {//统计连通分量的个数
    int i,cnt=0;
    for(i=0; i<n; i++) {
        if(f[i]==i)
            cnt++;
    }
    return cnt;
}
int main() {
    int Nv,Ne;
    scanf("%d %d",&Nv,&Ne);
    int i;
    int v1,v2;
    int G[Nv+1][Nv+1];
    memset(G,0,sizeof(G));
    
    Init(f,Nv);
    for(i=0; i<Ne; i++) {//图的初始化
        scanf("%d %d",&v1,&v2);
        merge(v1,v2);
        G[v1][v2]=G[v2][v1]=1;
    }
    int cnt1=Cnt(f,Nv);
    int k,x,j,s,t;
    scanf("%d",&k);
    for(i=0; i<k; i++) {
        scanf("%d",&x);
        for(j=0; j<Nv; j++) {//攻占一座城池后，更新图
            G[x][j]=0;
            G[j][x]=0;
        }
        Init(f,Nv);
        for(s=0; s<Nv; s++) {
            for(t=0; t<Nv; t++) {
                if(G[s][t]) {
                    merge(s,t);
                }
            }
        }
        int cnt2=Cnt(f,Nv);
        if(cnt2<=cnt1+1)
            printf("City %d is lost.",x);
        if(cnt2>cnt1+1)
            printf("Red Alert: City %d is lost!",x);
        cnt1=cnt2;
        cnt2=0;
        printf("
");
    }
    if(k==Nv)
    printf("Game Over.");
    printf("
");
    return 0;
}