有向图的强联通分量

时间:2020-12-27 17:53:05

  最近学了有向图的强联通分量。有kosaraju算法,不过写着比tarjin麻烦。所以就只记录tarjin算法。

  跟求无向图的双连通分量很相似,先贴代码。

 1 void dfs(int u){
 2     dfn[u]=low[u]=  clk;//dfn序 
 3     stk[top  ]=u;//压入栈内 
 4     for(int i=head[u];i;i=edge[i].nxt){
 5         int t=edge[i].to;
 6         if(dfn[t]==0){//如果下一个节点是没有访问过的 
 7             dfs(t);
 8             low[u]=min(low[u],low[t]);
 9         }
10         else if(sccno[v]==0)//如果下一个节点访问过,且该节点还不属于任何一个连通分量 
11             low[u]=min(low[u],dfn[v]);
12     }
13     if(low[u]==dfn[u]){
14         scccnt  ;//连通分量序号加 1 
15         while(top>0){
16             sccno[stk[--top]]=scccnt;
17             scc[scccnt].push_back(stk[top]);//用vector存储该连通分量 
18             if(stk[top]==u) break;//把当前节点u压入栈内为止 
19         }
20     }
21 }

 

  看一看例题。

 

  在数学中,我们经常要完成若干个命题的等价性证明。比如
  有4个命题a,b,c,d,我们证明a<->b,b<->c,最后c<->d。注意
  每次证明是双向的。因此一共完成了6次推导。另一种方法是
  证明a->b,b->c,c->d,d->a,这样就只需要4次推导。现在你的
  任务是证明n个命题全部等价,且你的朋友已经为你做出了m次
  推导(已知每次推导的内容),你至少还需要做几次推导才能
  完成证明?
  数据规模:T<=100,1<=n<=20000,1<=m<=50000

 

 

  很简单。先建图,然后tarjin出图的强联通分量,把所有分量缩成点

  图就变成了DAG图。这样原问题就变成了在这个DAG图中至少要添

  多少条边使该图变为一个强联通图。显然,我们只需求出入度为零

  的点的个数,和出度为零的点的个数,再取两者最大值即可(即从

  每个出度为零的点连接到每个入度为零的点,如果有多余的,多余的

  每个点随便连一条边都可。)