• 有向强连通分量（SCC）

    对于一个有向图，连通分量：对于分量中任意两点u,v，必然可以从u到v，从v到u

    强连通分量：最大连通分量

    作用：将任意一个有向图缩点（将所有连通分量缩成一个点）变成有向无环图（拓扑图）

     tarjan模板

    1. void tarjan(int u)
    2. {
    3.     dfn[u]=low[u]===timestamp;
    4.     stk[++top]=u,in_stk[u]=true;
    5.     for(int i=h[u];~i;i=ne[i])
    6.     {
    7.         int j=e[i];
    8.         if(!dfn[j])
    9.         {
    10.             tarjan(j);
    11.             low[u]=min(low[u],low[j]);
    12.         }
    13.         else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    14.     }
    15.     if(dfn[u]==low[u])
    16.     {
    17.         int y;
    18.         ++scc_cnt;//连通分量的个数
    19.         do
    20.         {
    21.             y=stk[top--];
    22.             in_stk[y]=false;
    23.             id[y]=scc_cnt;
    24.         }while(y!=u);
    25.     }
    26. }

    缩点（把强连通分量缩成一个点）

    目录

     1.受欢迎的牛

    2.学校网络

    3.最大半连通子图

    4.银河

    一般做法：

    1.tarjan

    2.缩点

    3.拓扑序递归求解

     1.受欢迎的牛

    信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

    1.tarjan

    2.缩点

    3.枚举求答案

    当操作了tarjan和缩点之后变成的拓扑图，假如有两个出度为0的点说明，这两个点互不可达，说明没有一头牛受任何牛欢迎

    假如有一个出度为0的点，说明这个点就是受所有牛欢迎的

    假如只有一个连通分量说明连通分量里的每头牛都互相受欢迎，则+连通分量牛的数量

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e4+10,M=5e4+10;
    5. int n,m;
    6. int h[N],e[M],ne[M],idx;
    7. int dfn[N],low[N],timestamp;//dfn是第一次遍历的时间戳，low是以当前点往下走的最早的时间戳
    8. int stk[N],top;
    9. bool in_stk[N];//标记是否在栈中
    10. int id[N],scc_cnt,size[N];//id表示每个点属于强连通分量那个编号，scc_cnt表示强连通分量的个数，size表示每个强连通分量点的数量
    11. int dout[N];//记录每个缩完点之后的出度是多少
    12. void add(int a,int b)
    13. {
    14.     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    15. }
    16. void tarjan(int u)
    17. {
    18.     low[u]=dfn[u]=++timestamp;//让他们都等于时间戳
    19.     stk[++top]=u,in_stk[u]=true;
    20.     for(int i=h[u];~i;i=ne[i])
    21.     {
    22.         int j=e[i];
    23.         if(!dfn[j])//假如没有遍历过
    24.         {
    25.             tarjan(j);
    26.             low[u]=min(low[u],low[j]);
    27.         }
    28.         else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    29.     }
    30.     if(dfn[u]==low[u])
    31.     {
    32.         ++scc_cnt;//连通分量++
    33.         int y;
    34.         do
    35.         {
    36.             y=stk[top--];
    37.             in_stk[y]=false;//不在栈中
    38.             id[y]=scc_cnt;//让这个点的编号等于这个连通分量
    39.             size[scc_cnt]++;//这个连通分量数量++
    40.         }while(y!=u);
    41.     }
    42. }
    43. int main()
    44. {
    45.     memset(h,-1,sizeof h);
    46.    cin>>n>>m;
    47.    while(m--)
    48.    {
    49.        int a,b;
    50.        cin>>a>>b;
    51.        add(a,b);
    52.    }
    53.    for(int i=1;i<=n;i++)//tarjan求强连通分量
    54.      if(!dfn[i])//假如没有遍历过
    55.         tarjan(i);
    56.    for(int u=1;u<=n;u++)//缩点
    57.       for(int i=h[u];~i;i=ne[i])
    58.       {
    59.           int j=e[i];
    60.           int a=id[u],b=id[j];
    61.           if(a!=b) dout[a]++;//假如不在一个连通分量里，则a在的连通分量出度++
    62.       }
    63.    int zeros=0,sum=0;
    64.    for(int i=1;i<=scc_cnt;i++)
    65.       if(!dout[i])
    66.       {
    67.           zeros++;
    68.           sum+=size[i];//假如连通分量的个数
    69.           if(zeros>1)//假如有多个连通分量的出度等于0，说明没有任何一头牛受欢迎
    70.           {
    71.               sum=0;
    72.               break;
    73.           }
    74.       }
    75.  cout<
    76.     return 0;
    77. }

    2.学校网络

    367. 学校网络 - AcWing题库

    1.tarjan

    2.缩点

    3.求入度与出度 

    入度为0的点是起点，出度为0的点是终点

    最少给的软件就是给起点

    建立的关系就起点与终点的最大值证明如下：

    设起点为n个，终点有m个，并且设n<=m

    1.当n==1时，直接把所有终点与起点相连就是所有都连通了则为m

    2.当n>1时，我们可以让一个终点与起点相连，这样终点与起点都-1，直到起点只有1个时，我们已经连了n-1对起点与终点，此时起点只有一个，终点变成m-(n-1)个，这是根据1情况要连m-(n-1)个，加上刚刚连的n-1条起点与终点，则总的连接为m-(n-1)+(n-1)=m条证毕

    当n>m也同理可证

    1. #include
    2. using namespace std;
    3. const int N=110,M=N*N;
    4. int n;
    5. int h[N],e[M],ne[M],idx;
    6. int dfn[N],low[N],timestamp;
    7. int stk[N],top;
    8. bool in_stk[N];
    9. int id[N],scc_cnt;
    10. int din[N],dout[N];
    11. void add(int a,int b)
    12. {
    13.     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    14. }
    15. void tarjan(int u)
    16. {
    17.     low[u]=dfn[u]=++timestamp;//获取这个位置的时间戳
    18.     stk[++top]=u,in_stk[u]=true;//标记这个点在栈里了
    19.     for(int i=h[u];~i;i=ne[i])
    20.     {
    21.         int j=e[i];
    22.         if(!dfn[j])//假如没有更新过
    23.         {
    24.             tarjan(j);
    25.             low[u]=min(low[u],low[j]);//更新一遍最小值
    26.         }
    27.         else if(in_stk[j]) low[u]=min(low[u],dfn[j]);//假如已经在栈里了，也更新最小值
    28.     }
    29.     if(low[u]==dfn[u])//假如搜索到头了
    30.     {
    31.         ++scc_cnt;//则最大强连通数量++
    32.         int y;
    33.         do
    34.         {
    35.             y=stk[top--];//取出栈顶
    36.             in_stk[y]=false;//标记不在栈中了
    37.             id[y]=scc_cnt;//让这个点归到强这个强连通分支中
    38.         }while(y!=u);
    39.     }
    40. }
    41. int main()
    42. {
    43.     memset(h,-1,sizeof h);
    44.     cin>>n;
    45.     for(int i=1;i<=n;i++)
    46.     {
    47.         int t;
    48.         while(cin>>t,t)
    49.         {
    50.             add(i,t);
    51.         }
    52.     }
    53.     for(int i=1;i<=n;i++)
    54.         if(!dfn[i])//假如还没搜索过
    55.             tarjan(i);
    56.    for(int u=1;u<=n;u++)//枚举缩点后的
    57.      for(int i=h[u];~i;i=ne[i])
    58.      {
    59.          int j=e[i];
    60.          int a=id[u],b=id[j];//获取两个分别所在的强连通分量中
    61.          if(a!=b) dout[a]++,din[b]++;//让a出度++，b入度++
    62.      }
    63.   int in=0,out=0;
    64.   for(int i=1;i<=scc_cnt;i++)//分别获取起点与终点，也就是入度为0的点与出度为0的点
    65.   {
    66.       if(!din[i]) in++;//入度为0是起点
    67.       if(!dout[i]) out++;//出度为0是终点
    68.   }
    69.   cout<//输出起点的数就是需要分发的个数
    70.   if(scc_cnt==1) puts("0");//假如只有一个强连通分支说明没有终点
    71.   else cout<<max(in,out)<//否则输出二者最大的数
    72.     return 0;
    73. }

    3.最大半连通子图

    信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

    1.tarjan

    2.缩点判重

    3.按照拓扑序递推

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10,M=2e6+10;
    5. int h[N],hs[N],e[M],ne[M],idx;//h是原来的图，hs是缩点后建的图
    6. int dfn[N],low[N],timestamp;
    7. int stk[N],top;
    8. bool in_stk[N];
    9. int id[N],scc_cnt,size[N];//size记录每个最大连通分量的数量
    10. int f[N],g[N];//f是点的个数，g是方案数
    11. int n,m,mod;
    12. unordered_set ha;//用来判重
    13. void add(int h[],int a,int b)
    14. {
    15.     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    16. }
    17. void tarjan(int u)//用tarjan搜索强连通分量
    18. {
    19.     dfn[u]=low[u]=++timestamp;
    20.     stk[++top]=u,in_stk[u]=true;
    21.     for(int i=h[u];~i;i=ne[i])
    22.     {
    23.         int j=e[i];
    24.         if(!dfn[j])
    25.         {
    26.             tarjan(j);
    27.             low[u]=min(low[u],low[j]);
    28.         }
    29.         else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    30.     }
    31.     if(dfn[u]==low[u])
    32.     {
    33.         ++scc_cnt;
    34.         int y;
    35.         do
    36.         {
    37.             y=stk[top--];
    38.             in_stk[y]=false;
    39.             size[scc_cnt]++;//该强连通分量个数加1
    40.             id[y]=scc_cnt;
    41.         }while(y!=u);
    42.     }
    43. }
    44. int main()
    45. {
    46.     memset(h,-1,sizeof h);
    47.     memset(hs,-1,sizeof hs);
    48.     scanf("%d%d%d",&n,&m,&mod);
    49.     while(m--)
    50.     {
    51.         int a,b;
    52.         scanf("%d%d",&a,&b);
    53.         add(h,a,b);
    54.     }
    55.     for(int i=1;i<=n;i++)//跑一遍tarjan合并强连通分量
    56.         if(!dfn[i])
    57.           tarjan(i);
    58.     for(int u=1;u<=n;u++)//建缩了点后的图
    59.         for(int i=h[u];~i;i=ne[i])
    60.         {
    61.            int j=e[i];
    62.            int a=id[u],b=id[j];
    63.            ll temp=a*1000000ll+b;
    64.            if(a!=b&&!ha.count(temp))//假如不在一个连通分量里和避免重复建边
    65.            {
    66.                add(hs,a,b);
    67.                ha.insert(temp);
    68.            }
    69.         }
    70.     //跑完tarjan得到的强连通分量就是一个拓扑序
    71.     for(int u=scc_cnt;u;u--)//从大到小就是拓扑序
    72.     {
    73.         if(!f[u]) f[u]=size[u],g[u]=1;//假如这个点没有点，则让这个f等于该连通分量的数，方案就自己一个
    74.         for(int i=hs[u];~i;i=ne[i])//枚举所有与他相连的强连通分量
    75.         {
    76.             int j=e[i];
    77.             if(f[u]+size[j]>f[j])//假如其他点的个数比我大，则更新
    78.             {
    79.                 f[j]=f[u]+size[j];//更新最大值
    80.                 g[j]=g[u];//方案数等于他的方案数
    81.             }
    82.             else if(f[u]+size[j]==f[j]) g[j]=(g[j]+g[u])%mod;//假如相等，则加上这个方案数
    83.         }
    84.     }
    85.     int maxf=0,sum=0;
    86.     for(int i=1;i<=scc_cnt;i++)//求最多的点的方案数
    87.         if(f[i]>maxf) maxf=f[i],sum=g[i];
    88.         else if(f[i]==maxf) sum=(sum+g[i])%mod;
    89.     printf("%d\n%d\n",maxf,sum);//输出最多的点和其方案数
    90.     return 0;
    91. }

    4.银河

    368. 银河 - AcWing题库

    这题跟糖果那一题一样，但是用差分约束解决的spfa会被卡掉，所以用最大连通分量保证o(n+m)不会被卡

    1.tarjan

    2.缩点

    3.依据拓扑序递推

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10,M=6e6+10;
    5. int n,m;
    6. int h[N],hs[N],e[M],ne[M],w[M],idx;
    7. int dfn[N],low[N],timestamp;
    8. int stk[N],top;
    9. bool in_stk[N];
    10. int id[N],scc_cnt,sizes[N];
    11. int dist[N];
    12. void add(int h[],int a,int b,int c)
    13. {
    14.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    15. }
    16. void tarjan(int u)//常规的tarjan模板
    17. {
    18.     dfn[u]=low[u]=++timestamp;
    19.     stk[++top]=u,in_stk[u]=true;
    20.     for(int i=h[u];~i;i=ne[i])
    21.     {
    22.         int j=e[i];
    23.         if(!dfn[j])
    24.         {
    25.             tarjan(j);
    26.             low[u]=min(low[u],low[j]);
    27.         }
    28.         else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    29.     }
    30.     if(low[u]==dfn[u])
    31.     {
    32.         ++scc_cnt;
    33.         int y;
    34.         do
    35.         {
    36.             y=stk[top--];
    37.             in_stk[y]=false;
    38.             id[y]=scc_cnt;
    39.             sizes[scc_cnt]++;
    40.         }while(y!=u);
    41.     }
    42. }
    43. int main()
    44. {
    45.     memset(h,-1,sizeof h);
    46.     memset(hs,-1,sizeof hs);
    47.    scanf("%d%d",&n,&m);
    48.    for(int i=1;i<=n;i++) add(h,0,i,1);//保证所有数都是大于1的
    49.    while(m--)
    50.    {
    51.        int t,a,b;
    52.        scanf("%d%d%d",&t,&a,&b);
    53.        if(t==1) add(h,a,b,0),add(h,b,a,0);
    54.        else if(t==2) add(h,a,b,1);
    55.        else if(t==3) add(h,b,a,0);
    56.        else if(t==4) add(h,b,a,1);
    57.        else add(h,a,b,0);
    58.    }
    59.    tarjan(0);//因为0号点跟所有点都连了边所以不用枚举其他点了
    60.    bool f=true;//判断是否有环
    61.   for(int u=0;u<=n;u++)
    62.   {
    63.     for(int i=h[u];~i;i=ne[i])
    64.       {
    65.         int j=e[i];
    66.         int a=id[u],b=id[j];
    67.         if(a==b)//一个环中，也就是一个连通分量中
    68.         {
    69.             if(w[i]>0)//最大连通量里的边权大于1，说明有正环
    70.             {
    71.                 f=false;
    72.                 break;
    73.             }
    74.         }
    75.         else add(hs,a,b,w[i]);//反之其他连通分量建边就是拓扑序
    76.       }
    77.       if(!f) break;
    78.   }
    79.   if(!f) puts("-1");
    80.   else
    81.   {
    82.       for(int u=scc_cnt;u;u--)//按照从大到小就是拓扑序
    83.         for(int i=hs[u];~i;i=ne[i])
    84.         {
    85.             int j=e[i];
    86.              dist[j]=max(dist[j],dist[u]+w[i]);//更新每个点的距离最大值
    87.         }
    88.      ll res=0;
    89.      for(int i=1;i<=scc_cnt;i++) res+=(ll)dist[i]*sizes[i];//最大距离就是该点的距离乘以点数
    90.      printf("%lld\n",res);
    91.   }
    92.     return 0;
    93. }

  • 相关阅读:
    shell第一次作业
    # 数值计算：三角形积分
    一、Flume使用
    2023-10-19 node.js-将异步处理修改为同步-使用Promise和async-记录
    iOS UIKit
    前端利用原生canvas生成图片
    夏日水果茶饮店如何引流？这四款饮品必学
    【Java】容器｜Set、List、Map及常用API
    【STM32】STM32学习笔记-修改主频 睡眠模式 停止模式 待机模式(45)
    mindspore构建网络时，自己定义的函数或层不能正常使用
  • 原文地址：https://blog.csdn.net/m0_63729880/article/details/126422527