PAT1013

思路分析:

这道题就是要去求一个图的联通分量数目。要求联通分量,当然就是得用BFS或者DFS来遍历图,以此来进行判断。

这道题中,我们会先得到一个图,接下来哪一个城市(节点)被占领,就不去考虑这个节点的相关信息来求联通分量。

避坑指南:

1.这道题给你的只是一个图,不要想多了,绝不是连通图,有可能有很多孤立的点点,所以一定要严格按照BFS或者DFS整个流程来

2.为了方便,我是从下标1才开始使用数组,所以有些地方要注意一下,比如循环、fill()的时候要注意范围

代码:

(1)BFS

int map[1001][1001];

int main(){
    freopen("in.txt","r",stdin);
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    while(m--){
        int from,to;
        scanf("%d %d",&from,&to);  //scanf里面的逗号,wtf 
        map[from][to]=1;
        map[to][from]=1;
    }
    
    while(k--){
        int city;
        scanf("%d",&city);
        int tag[1000]; //存储要进行广度搜索的值 ,全部都要探测 
        for(int i=1;i<=n;++i)  
            if(i!=city)
                tag[i]=1;
        int count=0;
        for(int i=1;i<=n;++i){
            if(tag[i]==1){
                count++;
                queue<int> q;  //BFS队列 
                q.push(i);
                int set[1000]={0}; //存放已经出了BFS队列的值
                set[city]=1;  //这样city就永远都不会被考虑进来 
                while(!q.empty()){
                    int now=q.front();
                    q.pop();
                    set[now]=1;
                    tag[now]=0;
                    for(int j=1;j<=n;++j){
                        if(set[j]==0 && map[now][j]==1){
                            q.push(j);
                        }    
                    }
                }
            } 
        }
        printf("%d",count-1);
        if(k!=0) printf("\n");            
    }
    return 0;
}

(2)DFS

int map[1001][1001];
bool visit[1001];
int n;
void dfs(int node){
    visit[node]=true;
    for(int i=1;i<=n;++i){
        if(visit[i]==false && map[node][i]==1)
            dfs(i);
    }
}

int main(){
    freopen("in.txt","r",stdin);
    int m,k;
    scanf("%d %d %d",&n,&m,&k);
    while(m--){
        int from,to;
        scanf("%d %d",&from,&to);  //scanf里面的逗号,wtf 
        map[from][to]=1;
        map[to][from]=1;
    }
    
    while(k--){
        int city;
        scanf("%d",&city);
        fill(visit,visit+(n+1),false);  //这里不能只加n,因为我们实际从下标1才开始使用,所以要比实际多1 
        int count=0;
        visit[city]=true;
        for(int i=1;i<=n;++i){
            if(visit[i]==false){
                count++;
                dfs(i);
            } 
        }
        printf("%d",count-1);
        if(k!=0) printf("\n");            
    }
    return 0;
}

 

上一篇:2021-10-18


下一篇:python中日志信息打不开时,处理的方法