PAT 1013 Battle Over Cities (25 分)

题意就是问你图中去掉一个点剩余的部分需要最少修几条路可以再次保证联通？

解法

我最初是想着把他们弄成点，然后10分，看网上老哥做法是看成联通快，把剩余的部分看成图，最后求图路径就是联通块个数-1即可

代码

#include <bits/stdc++.h>
using namespace std;
vector<int> G[2333];
int mk[2333],ans[2333],sum;
void dfs(int p)
{
  for(int i=0;i<G[p].size();i++)
  if(!mk[G[p][i]])
  {
    mk[G[p][i]]=1;
    dfs(G[p][i]);
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m,k;
  cin>>n>>m>>k;
  while(m--)
  {
    int st,ed;
    cin>>st>>ed;
    G[st].push_back(ed);
    G[ed].push_back(st);
  }
  while(k--)
  {
    int now;
    cin>>now;
    int sum=0;
    memset(mk,0,sizeof(mk));
    mk[now]=1;
    for(int j=1;j<=n;j++)
    if(!mk[j])
    {
      dfs(j);
      sum++;
    }
    cout<<sum-1<<"\n";
  }
}