PAT A1013 Battle Over Cities

这道题可以说是很经典的图论问题，个人觉得其主要的考点是连通量的计数问题；

对于这道题，起初看到，可能会反应不过来这是连通量计数问题，并且还尝试性的去考虑怎么连接连通分量；

这道题其实思路很清晰，自己接触到的有两种方法可以解这个问题：

1.使用深度或者广度遍历，确定出不连通的连通分量个数；

2.使用并查集，对于连通分量来说，可以确定出一个确切的集合，所以多个连通分量就是有多个并查集集合；

最后需要搭建的路径个数也就是：连通分量个数-1；

首先是并查集的思路解决方式：

对于并查集来说，当时也想到过。起先的想法是构建一个大的集合，通过删节点来分为两个小的集合。但是却遇到问题，当出现环的时候，删除一个节点可能会导致一个集合误判为两个集合的情况。但是解析思路是另一种思路。

起初构建图的时候并不建立并查集，而是在后续遍历的时候逐渐构造并查集，并且通过判断是否是同一个根节点来判断是否属于一个并查集集合；

例如如下代码所示：

PAT A1013 Battle Over Cities

其主调函数是Union，目的是在进行节点遍历的时候直接将属于同一个连通分量的节点构造成为同一颗子树。这里注意下，findFather（）函数中进行了路径压缩来降低访问时间，这也是很经典的一种操作；

PAT A1013 Battle Over Cities

如上所示，后续就是进行连通分量的确定。如果有多个连通分量，则并查集就会有多个根节点；所以进行枚举，如果发现不同的根节点，直接计数；

值得注意的是解析的方法中并没有对原图进行修改，而是直接对节点进行屏蔽操作，这也是很值得学习的方式；

总体代码如下所示：

#include<cstdio>
#include<vector>
#include<stdlib.h>
using namespace std;
const int N=1111;
vector<int> G[N];
int father[N];
bool vis[N];
int findFather(int x){
    int a=x;
    while(x!=father[x]){
        x=father[x];
    }
    //进行路径压缩
    while(a!=father[a]){
        int z=a;
        a=father[a];
        father[z]=x;
    }
    return x;
}
void Union(int a,int b){
    int faA=findFather(a);
    int faB=findFather(b);
    if(faA!=faB){
        father[faA]=faB;
    }
}
void init(){
    for(int i=1;i<N;i++){
        father[i]=i;
        vis[i]=false;
    }
}
int n,m,k;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int currentPoint;
    for(int query=0;query<k;query++){
        scanf("%d",&currentPoint);
        init();
        for(int i=1;i<=n;i++){
            for(int j=0;j<G[i].size();j++){
                int u=i,v=G[i][j];
                if(u==currentPoint||v==currentPoint)
                    continue;
                Union(u,v);
            }
        }
        int block=0;
        for(int i=1;i<=n;i++){
            if(i==currentPoint)
                continue;
            int fa_i=findFather(i);
            if(vis[fa_i]==false){
                block++;
                vis[fa_i]=true;
            }
        }
        printf("%d\n",block-1);
    }
    system("pause");
    return 0;
}

还有一种思路就是利用DFS来进行连通判定。总体思路就是每次访问一个起始点，然后进行DFS判定，如果还要再次遍历，则联通块+1；

值得注意的是需要注意DFS的高效书写模式，学习一下；

代码如下所示：

#include<cstdio>
#include<stdlib.h>
#include<cstring>
#include<vector>
using namespace std;
const int N=1111;
vector<int>G[N];
bool vis[N];
int currentPoint;
void dfs(int v){
    if(v==currentPoint)
        return;
    vis[v]=true;
    for(int i=0;i<G[v].size();i++){
        if(vis[G[v][i]]==false){
            dfs(G[v][i]);
        }
    }
}
int n,m,k;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int query=0;query<k;query++){
        scanf("%d",&currentPoint);
        for(int i=0;i<N;i++){
            vis[i]=false;
        }
        int block=0;//联通块个数
        for(int i=1;i<=n;i++){
            if(i!=currentPoint&&vis[i]==false){
                dfs(i);
                block++;
            }
        }
        printf("%d\n",block-1);
    }
    system("pause");
    return 0;
}

PAT A1013 Battle Over Cities

相关推荐