PAT甲级1013 Battle Over Cities 求图中最大连通量-蒲公英云

PAT甲级1013 Battle Over Cities 求图中最大连通量

在这里插入图片描述
解题思路：
1.求公路数关键是求出互不相连的城市群数，假设一块连通的城市群是一个结点，我们只需要求出所有结点数，然后公路树就是结点数-1
2.定义flag数组记录每个城市是否被访问过，path数组记录两个城市间是否有公路
3.dfs遍历图，递归条件是下一个城市没被访问，并且当前城市到下一个城市有路，一次dfs可以遍历一个城市群
4.最后写一个循环，从1到n循环遍历整个图，如果当前城市没被访问过，调用dfs，同时cnt++,最后初始化flag数组，然后输出cnt-1，就是我们要求的值

#include<iostream>
using namespace std;
int path[1005][1005];//记录两城市间是否有路
int flag[1005];
int n,m,k;
void dfs(int city)
{ 
    if(flag[city]==1)return;
    flag[city]=1;//标记为已经访问过
    for(int i=1;i<=n;i++)
    { 
        if(path[city][i]==1&&flag[i]==0)
        dfs(i);
    }
}
int main()
{ 
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    { 
        int a,b;
        cin>>a>>b;
        path[a][b]=path[b][a]=1;
    }
    int result;
    while(k--)
    { 
        int cnt=0;
        cin>>result;
        flag[result]=1;
        for(int i=1;i<=n;i++)
        { 
            if(flag[i]==0)
            { 
                dfs(i);
                cnt++;
            }
        }
        cout<<cnt-1<<endl;
        for(int i=1;i<=n;i++)flag[i]=0;//初始化
    }
    return 0;
}