• PAT A1013 Battle Over Cities分数 25（连通块数量，割点是针对连通块的，不是整个图）

    1013 Battle Over Cities

    分数 25

    作者 CHEN, Yue

    单位 浙江大学

    It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.

    For example, if we have 3 cities and 2 highways connecting city1​-city2​ and city1​-city3​. Then if city1​ is occupied by the enemy, we must have 1 highway repaired, that is the highway city2​-city3​.

    Input Specification:

    Each input file contains one test case. Each case starts with a line containing 3 numbers N (<1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.

    Output Specification:

    For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.

    Sample Input:

    1. 3 2 3
    2. 1 2
    3. 1 3
    4. 1 2 3

    Sample Output:

    1. 1
    2. 0
    3. 0


     * 求图的割点，割边只是针对连通块而言，并不是针对整个图。
     *
     * 对于此题，去掉某个点，进行图的遍历，求图的连通块数量，要整个图连通，则至少需要
     * 连通块数量减一 条边。
     *
     * 图的遍历用邻接表存储，需要O（M）的时间复杂度。共检测k个点，进行k遍图的遍历，
     * 总的时间复杂度为：O（M*K）；



    求图的割点，割边（啊哈算法）_疯疯癫癫才自由的博客-CSDN博客
     

    1)用图的割点算法加求连通块数量求解，有一个测试点通不过：

    1. /**
    2.  * 求图的割点，割边只是针对连通块而言，并不是针对整个图。
    3.  * 
    4.  * 对于此题，去掉某个点，进行图的遍历，求图的连通块数量，要整个图连通，则至少需要
    5.  * 连通块数量减一条边。
    6.  * 
    7.  * 图的遍历用邻接表存储，需要O（M）的时间复杂度。共检测k个点，进行k遍图的遍历，
    8.  * 总的时间复杂度为：O（M*K）；
    9. */
    10.  
    11.  
    12. #include <iostream>
    13. #include <algorithm>
    14. #include <vector>
    15.  
    16. using namespace std;
    17.  
    18. const int N = 1010;
    19. vector<int> Adj[N];
    20. int num[N], low[N];
    21. int flag[N];
    22. bool hs[N];
    23.  
    24. int idx, root;
    25. int Nv,Ne,k;
    26.  
    27. void dfs(int u, int fath)
    28. {
    29.     int child = 0;
    30.     ++idx;
    31.     num[u] = idx;
    32.     low[u] = idx;
    33.     
    34.     for(int i=0; i<Adj[u].size(); ++i)
    35.     {
    36.         int v = Adj[u][i];
    37.         if(num[v] == 0)
    38.         {
    39.             dfs(v, u);
    40.             low[u] = min(low[u], low[v]);
    41.             if(u != root && low[v] >= num[u])
    42.                 flag[u] = 1;
    43.             ++child;
    44.             if(u == root && child >= 2)
    45.                 flag[u] = 1;
    46.         }
    47.         else if(v != fath)
    48.             low[u] = min(low[u], num[v]); 
    49.     }
    50. }
    51.  
    52. void traver()
    53. {
    54.     for(int i=1; i<=Nv; ++i)
    55.         if(num[i] == 0)
    56.         {
    57.             root = i;
    58.             dfs(i, root);
    59.         }
    60. }
    61.  
    62. void DFS(int u, int rm)
    63. {
    64.     hs[u] = 1;
    65.     for(int i=0; i<Adj[u].size(); ++i)
    66.     {
    67.         int v = Adj[u][i];
    68.         if(hs[v] == 0)
    69.             DFS(v, rm);
    70.     }
    71. }
    72.  
    73. int FolldFill(int u)
    74. {
    75.     fill(hs,hs+N,0);
    76.     
    77.     hs[u] = 1;
    78.         
    79.     int cnt = 0;
    80.     for(int i = 1; i<=Nv; ++i)
    81.     {
    82.         if(hs[i] == 0)
    83.         {
    84.             DFS(i, u);
    85.             ++cnt;
    86.         }
    87.     }
    88.     return cnt;
    89. }
    90.  
    91. int main()
    92. {
    93.     cin >> Nv >> Ne >> k;
    94.     
    95.     int u, v;
    96.     while (Ne -- )
    97.     {
    98.         cin >> u >> v;
    99.         Adj[u].push_back(v);
    100.         Adj[v].push_back(u);
    101.     }
    102.     
    103.     traver();
    104.     
    105.     while(k--)
    106.     {
    107.         cin >> u;
    108.         if(flag[u] == 0)  //题目并不保证整个地图是只有一个连通块，所以此处并不能用
    109.             puts("0");  //割点算法来判断
    110.         else 
    111.             cout << FolldFill(u)-1 << endl;
    112.     }
    113.     
    114.     return 0;
    115. }

      * 求图的割点，割边只是针对连通块而言，并不是针对整个图。
     *
     * 对于此题，去掉某个点，进行图的遍历，求图的连通块数量，要整个图连通，则至少需要
     * 连通块数量减一条边。
     *
     * 图的遍历用邻接表存储，需要O（M）的时间复杂度。共检测k个点，进行k遍图的遍历，
     * 总的时间复杂度为：O（M*K）；

    2）AC代码，连通块数量求解：

    1. /**
    2.  * 求图的割点，割边只是针对连通块而言，并不是针对整个图。
    3.  * 
    4.  * 对于此题，去掉某个点，进行图的遍历，求图的连通块数量，要整个图连通，则至少需要
    5.  * 连通块数量减一条边。
    6.  * 
    7.  * 图的遍历用邻接表存储，需要O（M）的时间复杂度。共检测k个点，进行k遍图的遍历，
    8.  * 总的时间复杂度为：O（M*K）；
    9. */
    10.  
    11. #include <iostream>
    12. #include <algorithm>
    13. #include <vector>
    14.  
    15. using namespace std;
    16.  
    17. const int N = 1010;
    18. vector<int> Adj[N];
    19. bool hs[N];
    20.  
    21. int Nv,Ne,k;
    22.  
    23. void DFS(int u, int rm)
    24. {
    25.     hs[u] = 1;
    26.     for(int i=0; i<Adj[u].size(); ++i)
    27.     {
    28.         int v = Adj[u][i];
    29.         if(hs[v] == 0)
    30.             DFS(v, rm);
    31.     }
    32. }
    33.  
    34. int FolldFill(int u)
    35. {
    36.     fill(hs,hs+N,0);
    37.     
    38.     hs[u] = 1; //先把顶点u去掉
    39.         
    40.     int cnt = 0;
    41.     for(int i = 1; i<=Nv; ++i)
    42.     {
    43.         if(hs[i] == 0)
    44.         {
    45.             DFS(i, u);
    46.             ++cnt;
    47.         }
    48.     }
    49.     return cnt;
    50. }
    51.  
    52. int main()
    53. {
    54.     cin >> Nv >> Ne >> k;
    55.     
    56.     int u, v;
    57.     while (Ne -- )
    58.     {
    59.         cin >> u >> v;
    60.         Adj[u].push_back(v);
    61.         Adj[v].push_back(u);
    62.     }
    63.     
    64.     while(k--)
    65.     {
    66.         cin >> u;
    67.         cout << FolldFill(u)-1 << endl;
    68.     }
    69.     
    70.     return 0;
    71. }

    3）割点 + 连通块求解

     * 倒是也可以用割点算法来求解，但是割点是针对连通图而言，所以需要是对整个图的
     * 所有连通块都进行割点求解，然后再求解出整个图的连通块个数，并且把每个连通块
     * 的顶点个数求解出来，假定此时求出的连通块个数为cnt，
     * 1）如果有孤立的点存在，敌人把此点占用，那么连通块个数减一，所以需要连的边
     * 数为 cnt - 2；
     * 2）如果敌人占用的点为割点，那么需要连的边数为 cnt；
     * 3）如果敌人占用的点只是某个连通块中顶点个数不为1的其中的一个点，那么需要
     * 连的边数为 cnt - 1；
     *
     * 此种做法确实比较繁琐，没有 直接去掉某个点，求出 去掉此点后的图中的连通块的
     * 数量，然后用数量减一就是所需连的边数，即答案 那么简便；但是前者的时间复杂
     * 度是线性的，而后者的时间复杂度是 O(K * M),是二次方复杂度，对于边数较大的题
     * 就有可能会超时。

    1. /**
    2.     时间戳：深度优先遍历时，访问每个节点的先后顺序从 1到n；
    3.     使用 num[] 来记录每个顶点的先后顺序；
    4.     满足割点的条件：子节点 v 不经过父节点 u 是不能达到u的祖宗节点的（也就是已经被访问
    5.     的那些节点）；
    6.     使用 low[] 来记录每个节点不经过父节点能到达的最早顶点的时间戳；
    7.     因此满足割点的结点是： low[v] >= num[u] ；意思是子节点v不经过父节点u能到达的最早时间
    8.     戳也不过是u，那么把u去掉，不就能把图分成两部分了；但是这也仅仅是来检测非根节点的方法，
    9.     根节点是否为割点还要特判，如果根节点的子节点有两个孩子，且两个孩子不能相互到达，那么
    10.     根节点就是割点；
    11. */
    12.  
    13.  
    14. /**
    15.  * 倒是也可以用割点算法来求解，但是割点是针对连通图而言，所以需要是对整个图的
    16.  * 所有连通块都进行割点求解，然后再求解出整个图的连通块个数，并且把每个连通块
    17.  * 的顶点个数求解出来，假定此时求出的连通块个数为cnt，
    18.  * 1）如果有孤立的点存在，敌人把此点占用，那么连通块个数减一，所以需要连的边
    19.  * 数为 cnt - 2；
    20.  * 2）如果敌人占用的点为割点，那么需要连的边数为 cnt；
    21.  * 3）如果敌人占用的点只是某个连通块中顶点个数不为1的其中的一个点，那么需要
    22.  * 连的边数为 cnt - 1；
    23.  * 
    24.  * 此种做法确实比较繁琐，没有 直接去掉某个点，求出 去掉此点后的图中的连通块的
    25.  * 数量，然后用数量减一就是所需连的边数，即答案 那么简便；但是前者的时间复杂
    26.  * 度是线性的，而后者的时间复杂度是 O(K * M),是二次方复杂度，对于边数较大的题
    27.  * 就有可能会超时。
    28. */
    29.  
    30. #include <iostream>
    31. #include <algorithm>
    32. #include <vector>
    33.  
    34. using namespace std;
    35.  
    36. const int maxn = 1e5+10;
    37. vector<int> Adj[maxn];  ///邻接表
    38. int num[maxn] , low[maxn] ; ///时间戳
    39. int flag[maxn]; ///顶点编号是割点则记为1，否则为0；
    40. int root , index; ///root为根节点，index为时间戳
    41.  
    42. void dfs(int u,int fath)    ///fath为u的父节点
    43. {
    44.     int child = 0;  ///u的子节点数目
    45.     ++index;    ///时间戳加一
    46.     num[u] = index;
    47.     low[u] = index; ///最开始时间戳就是自己
    48.     for(int i=0;i<Adj[u].size();++i)
    49.     {
    50.         int v = Adj[u][i];
    51.         if(num[v] == 0) ///如果v还没被访问过
    52.         {
    53.             ++child;    ///将v归为u的子节点，子节点数目加一
    54.             dfs(v,u);   ///递归
    55.             low[u] = min(low[u] , low[v]);  ///要将u的时间戳（是low，不是num）更新
    56.             if(u != root && low[v] >= num[u]) ///如果u不是根节点，并且满足割点的条件
    57.             {
    58.                 flag[u] = 1;
    59.             }
    60.             ///如果u是根节点且孩子节点也有两个，那么根节点就是割点；
    61.             ///并且我们能证明出两个孩子节点一定不能通过若干结点中转相互到达；
    62.             ///假设能相互到达，那么这两个孩子节点一定不能共同车成为u的孩子节点，
    63.             ///因为一个孩子节点进行递归以后，会把该孩子节点能够连通且没有被访问的结点
    64.             ///进行访问；
    65.             if(u == root && child == 2)
    66.             {
    67.                 flag[u] = 1;
    68.             }
    69.         }
    70.  
    71.         ///如果v已经被访问过且是u的祖宗节点（并不是父节点），则更新当前节点 u 能否
    72.         ///访问到最早顶点的时间戳；
    73.         else if(v != fath)
    74.             low[u] = min(low[u] , num[v]);
    75.     }
    76. }
    77.  
    78. int id[maxn], Size[maxn];
    79. int stk[maxn];
    80. bool hs[maxn];
    81. int cnt, top;
    82.  
    83. void FloodFill(int u)
    84. {
    85.     hs[u] = 1;
    86.     stk[top++] = u; //将u入栈，在栈中的所有顶点都是属于同一个连通块中；
    87.     
    88.     for(auto v : Adj[u])
    89.         if(hs[v] == 0)
    90.             FloodFill(v);
    91. }
    92.  
    93. int main()
    94. {
    95.     int n,m, k;
    96.     cin >> n >> m >> k;
    97.     for(int i=0;i<m;++i)
    98.     {
    99.         int u,v;
    100.         cin >> u >> v;
    101.         Adj[u].push_back(v);
    102.         Adj[v].push_back(u);
    103.     }
    104.     
    105.     for(int i=1 ;i<=n; ++i)
    106.         if(hs[i] == 0)
    107.         {
    108.             FloodFill(i);
    109.             ++cnt;
    110.             int y;
    111.             do{
    112.                 y = stk[--top];
    113.                 id[y] = cnt; //顶点编号属于cnt这个连通块
    114.                 Size[cnt]++; //cnt连通块个数加一
    115.             }while(y != i);
    116.         }
    117.             
    118.     for(int i=1; i<=n; ++i)
    119.     {
    120.         root = i;
    121.         if(num[i] == 0)
    122.             dfs(i,-1); //求割点
    123.     }
    124.     
    125.     while(k--)
    126.     {
    127.         int chk;
    128.         cin >> chk;
    129.         if(flag[chk])   cout << cnt << endl; //割点
    130.         else if(Size[id[chk]] == 1) cout << cnt - 2 << endl; //孤立的点
    131.         else cout << cnt - 1 << endl; 
    132.     }
    133.     
    134.     return 0;
    135. }

  • 相关阅读:
    箭头函数
    微服务项目：尚融宝（45）（核心业务流程：借款申请（2））
    基于微信小程序的药店管理系统设计与实现-计算机毕业设计源码+LW文档
    Wnmp服务安装并结合内网穿透实现公网远程访问——“cpolar内网穿透”
    研发项目管理改进方法有哪些
    【自然语言处理】【向量检索】面向开发域稠密检索的多视角文档表示学习
    CSDN一站式云服务开放内测，诚邀C站新老用户来抢鲜
    Linux学习-71-GRUB手动安装方法
    Golang 笔试面试学习第一天之defer
    c++ 二分查找
  • 原文地址：https://blog.csdn.net/qq_51825761/article/details/127951628