PAT_A1013#Battle Over Cities

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

• 图的存储和遍历

Attention:

• 逻辑上删除结点即可，即遍历到w时直接return

Code:

 /*

 Data: 2019-05-16 21:26:01

 Problem: PAT_A1013#Battle Over Cities

 AC: 24:40

 题目大意：

 给一个图，拿掉一个顶点及其边，问至少添加几条边，可以保证图的连通

 输入：

 第一行给出：结点数N<1e3，边数M，查询次数K

 接下来M行，给出V1和V2，表示结点间存在边

 接下来一行，依次给出破坏顶点序号（1~N），输出需要添加的边数

 */

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int M=1e3+,INF=1e9;

 int grap[M][M],vis[M],n,m,k,w;

 void DFS(int u)

 {

     if(u==w)

         return;

     vis[u]=;

     for(int v=; v<=n; v++)

         if(vis[v]== && grap[u][v]==)

             DFS(v);

 }

 int Travel()

 {

     int cnt=-;

     fill(vis,vis+M,);

     for(int i=; i<=n; i++)

     {

         if(vis[i]== && i!=w)

         {

             DFS(i);

             cnt++;

         }

     }

     return cnt;

 }

 int main()

 {

 #ifdef  ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDGE

     scanf("%d%d%d", &n,&m,&k);

     fill(grap[],grap[]+M*M, INF);

     for(int i=; i<m; i++)

     {

         int v1,v2;

         scanf("%d%d",&v1,&v2);

         grap[v1][v2]=;

         grap[v2][v1]=;

     }

     for(int i=; i<k; i++)

     {

         scanf("%d", &w);

         printf("%d\n", Travel());

     }

     return ;

 }