• 有向图的强连通分量——学校网络


    二次元入口:367. 学校网络 - AcWing题库

    思路:

    根据题目建好有向图后走一遍tarjan算法获得强连通分量,记录每一个点的入度和出度,一个点在得到的强连通分量图里面是起点的话入度会是0,是终点的话出度会是0.

    对于第一个问题,需要至少直接提供给多少个学校,就是提供给拓扑图中的所有起点的强连通分量,起点的数量就是第一问的答案。

    第二问答案的结论是设拓扑图里面的起点数量为a,终点的数量为b,答案是max(a,b).

    第一问的证明很好想,第二问证明?我也还没完全看懂。

    证明:

    假设起点的数量p,终点的数量是q(以下的连边操作都是在缩完点后的拓扑图上面进行)

    特判:当强连通分量只有一个时,答案为0.

    在p<=q时

    1.当p==1,需要从q个终点都连一条边连向起点,这样才能使得从任意一个强连通分量出发都可以走到任意一个节点。(比较好想)

    2.当p>1时,有q>=p>=1,这时候,必定会有两个起点p1,p2,和两个终点q1,q2

    使得p1能够走到q1 , p2能够走到q2,从q1连一条边到p2,  p和q同时减1,相当于同时减少了一个起点和一个终点。

    按照这个操作进行p-1次,最后变成情形1,此时已经连的边的数量就是p-1,还需要连的边的数量就是q-(p-1),加起来就是q条

    代码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. typedef long long ll;
    7. const int N=110,M=1e4+10;
    8. int e[M],ne[M],h[N],idx;
    9. int dfn[N],times,low[N];
    10. int stk[N],top;
    11. bool in_stk[N];
    12. int id[N],scc_cnt;
    13. int din[N],dout[N];
    14. int n;
    15. void add(int a,int b)
    16. {
    17. e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    18. }
    19. void tarjan(int u)
    20. {
    21. dfn[u]=low[u]=++times;
    22. stk[++top]=u;
    23. in_stk[u]=true;
    24. for(int i=h[u];~i;i=ne[i])
    25. {
    26. int j=e[i];
    27. if(!dfn[j])
    28. {
    29. tarjan(j);
    30. low[u]=min(low[u],low[j]);
    31. }else if(in_stk[j])
    32. low[u]=min(low[u],dfn[j]);
    33. }
    34. if(low[u]==dfn[u])
    35. {
    36. ++scc_cnt;
    37. int y;
    38. do{
    39. y=stk[top--];
    40. in_stk[y]=false;
    41. id[y]=scc_cnt;
    42. }while(y!=u);
    43. }
    44. }
    45. int main()
    46. {
    47. scanf("%d",&n);
    48. memset(h,-1,sizeof h);
    49. for(int i=1;i<=n;i++)
    50. {
    51. int t;
    52. while(cin>>t,t) add(i,t);
    53. }
    54. for(int i=1;i<=n;i++)
    55. if(!dfn[i])
    56. tarjan(i);
    57. for(int i=1;i<=n;i++)
    58. for(int j=h[i];~j;j=ne[j])
    59. {
    60. int k=e[j];
    61. int a=id[i],b=id[k];
    62. if(a!=b)
    63. {
    64. dout[a]++;
    65. din[b]++;
    66. }
    67. }
    68. int a=0,b=0;
    69. for(int i=1;i<=scc_cnt;i++)
    70. {
    71. if(!din[i])
    72. {
    73. a++;
    74. }
    75. if(!dout[i]) b++;
    76. }
    77. printf("%d\n",a);
    78. if(scc_cnt==1) puts("0");
    79. else printf("%d\n",max(a,b));
    80. return 0;
    81. }

  • 相关阅读:
    10道不得不会的Docker面试题
    记一次因为没有关闭 管道导致的内存泄露
    Go:DoublyLinkedList双链表(附完整源码)
    场景案例│数字员工在物流行业的落地应用
    Redis布隆过滤器
    Android毕业设计开题报告基于Uniapp+SSM实现的公园植物介绍APP
    Lua使用三目运算符取值
    awoo‘s Favorite Problem(优先队列)
    vue中el-button防止重复点击
    YB4019是一款完整的单电池锂离子恒流/恒压线性充电器电池
  • 原文地址:https://blog.csdn.net/m0_62327332/article/details/127129252