有向圖的強(qiáng)連通分量

對(duì)于一個(gè)有向圖，連通分量：對(duì)于分量中任意兩點(diǎn)u,v，必然可以從u走到v,且從v走到u.
強(qiáng)連通分量：極大連通分量。
求出強(qiáng)連通分量后，可以通過(guò)將強(qiáng)連通分量縮點(diǎn)的方式，將有向圖轉(zhuǎn)化成有向無(wú)環(huán)圖。
求強(qiáng)連通分量的方法：tarjan O(n+m),時(shí)間復(fù)雜度是線性的
1 . 采用dfs來(lái)遍歷整個(gè)圖，可以將邊分為四類 （x->y）

• 樹枝邊 x是y的父節(jié)點(diǎn)
• 前向邊 x是y的祖先，x可以到達(dá)y
• 后向邊 y是x的祖先, x可以到達(dá)y
• 橫叉邊 x可以到達(dá)已經(jīng)遍歷且已經(jīng)回溯過(guò)的y點(diǎn)

2 .如何確定點(diǎn)在連通分量中

• 存在一條后向邊，使其指向祖先節(jié)點(diǎn)
• 存在一條橫插邊，走過(guò)了橫叉邊，又存在一條后向邊指向原來(lái)的點(diǎn)的祖先節(jié)點(diǎn)

3 .引入一個(gè)時(shí)間戳的概念

• dfn[u] 表示遍歷到u的時(shí)間,也就是dfs序
• low[u] 表示從u所在強(qiáng)連通分量中，所能遍歷到的層次最高的點(diǎn)的dfs序。
• 當(dāng)dfs[u]==low[u]時(shí)，表示u是其所在的強(qiáng)連通分量的最高點(diǎn)

4 . 對(duì)于tarjan算法,我的理解是每次都是對(duì)以當(dāng)前的點(diǎn)為根節(jié)點(diǎn)的子圖進(jìn)行操作的，遍歷完子圖中的所有點(diǎn)時(shí)，如果dfs[u]==low[u]表示當(dāng)前的根就是在強(qiáng)連通圖中，一個(gè)一個(gè)清掉棧中的元素，在沒有清掉當(dāng)前點(diǎn)的時(shí)候，清理出的元素都是強(qiáng)連通圖中的元素。

int n,m;
int h[N],ne[M],e[N],idx=0;
int dfn[N],low[N],tm=0;
int vis[N];
int id[N],cnt=0,ids[N];
int dout[N];
stack<int> s;

void add(int a,int b)
{
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
  dfn[u]=low[u]=++tm;
  s.push(u);
  vis[u]=1;
  for(int i=h[u];~i;i=ne[i])
  {
     int j=e[i];
     if(!dfn[j])
     { 
           tarjan(j);
           low[u]=min(low[u],low[j]);
     }
     else if(vis[j]) low[u]=min(low[u],dfn[j]);
  }

   if(dfn[u]==low[u])
   {
    ++cnt;
    int y;
    do{
       y=s.top();
       s.pop();
       vis[y]=0;
       id[y]=cnt;
       ids[cnt]++;
    }while(y!=u);
   }
}

總結(jié)：使用完tarjan算法后，就已經(jīng)將有向圖轉(zhuǎn)化為有向無(wú)環(huán)圖（DAG）。
而對(duì)于有向無(wú)環(huán)圖，有以下幾種應(yīng)用：（注意以下的點(diǎn)是經(jīng)過(guò)縮點(diǎn)之后的，點(diǎn)代表的是一個(gè)強(qiáng)連通分量，其中的點(diǎn)的個(gè)數(shù)為非零個(gè)）

1 是否存在點(diǎn)能被其他所有點(diǎn)到達(dá)。
只需計(jì)算出度為零的點(diǎn)有幾個(gè)：

• 有一個(gè)的話，表示存在，個(gè)數(shù)為當(dāng)前連通快的大小。
• 有多個(gè)的話，則為零個(gè)

2 選取最少的點(diǎn)數(shù)，即可遍歷整個(gè)圖

• 找出入度為零的強(qiáng)連通塊數(shù)，即為答案。（強(qiáng)連通塊中的點(diǎn)互相可以到達(dá)）

3 需要添加最少的邊數(shù)，使整個(gè)圖變?yōu)閺?qiáng)連通分量文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-497362.html

• 當(dāng)強(qiáng)連通塊的數(shù)量為1時(shí)，不需要加邊
• 不為1時(shí)，答案為在入度為零的點(diǎn)個(gè)數(shù)和出度為零的點(diǎn)個(gè)數(shù)取最大值，因?yàn)樽顑?yōu)情況時(shí)，每個(gè)出度為零的點(diǎn)向入度為零的點(diǎn)加一條邊，反之亦然。

到了這里，關(guān)于有向圖的強(qiáng)連通分量的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！