强连通分量初探 By cellur925

并不理解。但是毕竟也做了一些题，略微小结。

注：这里讨论的暂时是有向图的强联通分量。

先贴出模板。学长：我也不理解，但我可以叫你们怎么背代码。

 #include<cstdio>

 #include<algorithm>

 #include<stack>

 #define maxn

 using namespace std;

 int dfn[maxn],low[maxn]

 void dfs(int p)

 {

     dfn[p]=low[p]=++dfs_clock;

     s.push(p);

     for(int i=head[p];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(!dfn[y])

         {

             dfs(y);

             low[p]=min(low[p],low[y]);

         }

         else if(!scc[y]) low[p]=min(low[p],dfn[y]);

     }

     if(dfn[p]==low[p])

     {

         scc_cnt++;

         while()

         {

             int x=s.top();

             s.pop();

             scc[x]=scc_cnt;

             if(x==p) break;

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

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

      //读入边信息

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

     {

         if(!dfn[i]) dfs(i);

         tong[scc[i]]++;

         //scc[i]->i点在哪个强连通分量

         //tong[i]-> 第i个强连通分量大小

     }

     return ;

 }

一缩点

一句话来说，就是求出有向图中的强联通分量后，把每个强联通分量用一个点代替，得到一个DAG（有向无环图）。

我们用一个新的邻接表来记录新的DAG上的边。

这个过程可以近似的理解为缩点。先放下求缩点的模板。

 #include<cstdio>

 #include<algorithm>

 #include<stack>

 #include<queue>

 #include<cstring>

 using namespace std;

 //tarjan_need

 int n,m,x,y,tot,qwq,ans,scc_cnt,dfs_clock,sum[],pv[],head[],head_DAG[],low[],dfn[],scc[];

 struct node{

     int next,to;

 }edge[];

 struct nodee{

     int next,to;

 }edge_DAG[];

 stack<int>s;

 void add(int x,int y,int op)

 {

     if(op==)

     {

         edge[++tot].to=y;

         edge[tot].next=head[x];

         head[x]=tot;

     }

     else if(op==)

     {

         edge_DAG[++qwq].to=y;

         edge_DAG[qwq].next=head_DAG[x];

         head_DAG[x]=qwq;

     }

 }

 void tarjan(int p)

 {

     dfn[p]=low[p]=++dfs_clock;

     s.push(p);

     for(int i=head[p];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(!dfn[y])

         {

             tarjan(y);

             low[p]=min(low[p],low[y]);

         }

         else if(!scc[y]) low[p]=min(low[p],dfn[y]);

     }

     if(dfn[p]==low[p])

     {

         scc_cnt++;

         while()

         {

             int x=s.top();

             s.pop();

             scc[x]=scc_cnt;

             if(x==p) break;

         }

     }

 }

 int main()

 {

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

     for(int i=;i<=n;i++) scanf("%d",&pv[i]);

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

         scanf("%d%d",&x,&y),add(x,y,);

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

         if(!dfn[i]) tarjan(i);

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

         for(int i=head[x];i;i=edge[i].next)

             {

                 int y=edge[i].to;

                 if(scc[x]!=scc[y])

                     add(scc[x],scc[y],);

             }

     return ;

 }

然鹅洛谷的模板题更深一步，求：

给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

我们跑一遍tarjan进行缩点，得到一个新的DAG，在DAG上枚举起点，各跑一遍spfa求最长路，每跑完再枚举终点。注意这里是点带权而不是边带权，在进行强联通分量个数划分的时候，我们需要更新合并每个SCC的点权和（注意用新的数组保存！被这个地方卡了）。

（其实还有一种缩点后dp的做法，用拓扑排序处理掉dp后效性）

 #include<cstdio>

 #include<algorithm>

 #include<stack>

 #include<queue>

 #include<cstring>

 using namespace std;

 //tarjan_need

 int n,m,x,y,tot,qwq,ans,scc_cnt,dfs_clock,sum[],pv[],head[],head_DAG[],low[],dfn[],scc[];

 struct node{

     int next,to;

 }edge[];

 struct nodee{

     int next,to;

 }edge_DAG[];

 stack<int>s;

 //spfa_need

 int dis[];

 bool vis[];

 void add(int x,int y,int op)

 {

     if(op==)

     {

         edge[++tot].to=y;

         edge[tot].next=head[x];

         head[x]=tot;

     }

     else if(op==)

     {

         edge_DAG[++qwq].to=y;

         edge_DAG[qwq].next=head_DAG[x];

         head_DAG[x]=qwq;

     }

 }

 void tarjan(int p)

 {

     dfn[p]=low[p]=++dfs_clock;

     s.push(p);

     for(int i=head[p];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(!dfn[y])

         {

             tarjan(y);

             low[p]=min(low[p],low[y]);

         }

         else if(!scc[y]) low[p]=min(low[p],dfn[y]);

     }

     if(dfn[p]==low[p])

     {

         scc_cnt++;

         while()

         {

             int x=s.top();

             s.pop();

             scc[x]=scc_cnt;

             sum[scc_cnt]+=pv[x];

             if(x==p) break;

         }

     }

 }

 void spfa(int start)

 {

     memset(dis,,sizeof(dis));

     memset(vis,,sizeof(vis));

     queue<int>q;

     q.push(start);dis[start]=sum[start];vis[start]=;

     while(!q.empty())

     {

         int x=q.front();q.pop();vis[x]=;

         for(int i=head_DAG[x];i;i=edge_DAG[i].next)

         {

             int y=edge_DAG[i].to;

             if(dis[y]<dis[x]+sum[y])

             {

                 dis[y]=dis[x]+sum[y];

                 if(!vis[y])

                 {

                     vis[y]=;

                     q.push(y);

                 }

             }

         }

     }

     for(int i=;i<=scc_cnt;i++) ans=max(ans,dis[i]);

 }

 int main()

 {

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

     for(int i=;i<=n;i++) scanf("%d",&pv[i]);

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

         scanf("%d%d",&x,&y),add(x,y,);

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

         if(!dfn[i]) tarjan(i);

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

         for(int i=head[x];i;i=edge[i].next)

             {

                 int y=edge[i].to;

                 if(scc[x]!=scc[y])

                     add(scc[x],scc[y],);

             }

     for(int i=;i<=scc_cnt;i++) spfa(i);

     printf("%d",ans);

     return ;

 }

二、受欢迎的牛

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

题意可以再简化：给定一个有向图，问有多少个顶点是由任何顶点出发都可达的。

分析：（抄lyc课件）

• 有向无环图中唯一出度为 0 的点，一定可以由任何点出发均可达
• 由于无环，所以从任何点出发往前走，必然终止于一个出度为0
的点

• 求出所有强连通分量，每个强连通分量缩成一点，形成一个有向
无环图DAG。
• DAG上面如果恰有一个出度为0的点，说明DAG所有的点可到达这
个点，这个点是原图中的强连通分量，该强连通分量的点数，就
是答案。
• DAG上面如果有不止一个出度为0的点，因为它们不能互相到达，
故原问题无解，答案为0

code

 #include<cstdio>

 #include<algorithm>

 #include<stack>

 using namespace std;

 int n,m,tot,qwq,Chemist,cellur,dfs_clock,scc_cnt,qaq,qaqaq;

 int head[],head_DAG[],dfn[],low[],scc[],du[],tong[];

 struct node{

     int to,next;

 }edge[];

 stack<int>s;

 void add(int x,int y,int op)

 {

     if(op==)

     {

         edge[++tot].to=y;

         edge[tot].next=head[x];

         head[x]=tot;

     }

 }

 void dfs(int p)

 {

     dfn[p]=low[p]=++dfs_clock;

     s.push(p);

     for(int i=head[p];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(!dfn[y])

         {

             dfs(y);

             low[p]=min(low[p],low[y]);

         }

         else if(!scc[y]) low[p]=min(low[p],dfn[y]);

     }

     if(dfn[p]==low[p])

     {

         scc_cnt++;

         while()

         {

             int x=s.top();

             s.pop();

             scc[x]=scc_cnt;

             if(x==p) break;

         }

     }

 }

 int main()

 {

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

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

         scanf("%d%d",&Chemist,&cellur),add(Chemist,cellur,);

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

     {

         if(!dfn[i]) dfs(i);

         tong[scc[i]]++;

     }

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

         for(int i=head[x];i;i=edge[i].next)

             {

                 int y=edge[i].to;

                 if(scc[x]!=scc[y]) du[scc[x]]++;

             } 

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

          if(du[i]==) qaq++,qaqaq=i;

     if(qaq==) printf("%d",tong[qaqaq]);

     else printf("");

     return ;

 }

三、信息传递

题目描述

有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，

其中，编号为 ii 的同学的信息传递对象是编号为 Ti 的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

题意也是比较明白，求图中的最小环，我们可以用tarjan求（虽然有些小题大做的嫌疑）。记录各个强联通分量的大小，最后找最小的大于1的环就行了。

code

 #include<cstdio>

 #include<algorithm>

 #include<stack>

 #define maxn 200090

 using namespace std;

 int n,y,tot,ans=,dfs_clock,scc_cnt,tong[maxn],dfn[maxn],low[maxn],head[maxn],scc[maxn];

 stack<int>s;

 struct node{

     int to,next;

 }edge[maxn];

 void add(int x,int y)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 void dfs(int p)

 {

     dfn[p]=low[p]=++dfs_clock;

     s.push(p);

     for(int i=head[p];i;i=edge[i].next)

     {

         int y=edge[i].to;

         if(!dfn[y])

         {

             dfs(y);

             low[p]=min(low[p],low[y]);

         }

         else if(!scc[y]) low[p]=min(low[p],dfn[y]);

     }

     if(dfn[p]==low[p])

     {

         scc_cnt++;

         while()

         {

             int x=s.top();

             s.pop();

             scc[x]=scc_cnt;

             if(x==p) break;

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

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

      scanf("%d",&y),add(i,y);

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

     {

         if(!dfn[i]) dfs(i);

         tong[scc[i]]++;

     }

     for(int i=;i<=scc_cnt;i++) if(tong[i]>&&tong[i]<ans) ans=tong[i];

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

     return ;

 }

巴特西

强连通分量初探 By cellur925

题目描述

题目描述

最新文章

热门文章