生活随笔
收集整理的這篇文章主要介紹了
有向图——强连通分量
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
? ? 有向圖的強連通分量(strongly?connected components)
在有向圖G中，如果兩個頂點vi,vj間(vi!=vj)有一條從vi到vj的路徑，同時還有一條從vj到vi的路徑(頂點相互可達)，則稱兩個頂點強連通。如果有向圖G的每對頂點都強連通，稱G是個強連通圖。非強連通圖有向圖的極大強連通子圖，稱為強連通分量。
??? 求解強連通分量的算法主要有三種：Kosaraju，Tarjan，Gabow。下面介紹Tarjan算法。
??? Tarjan算法基于圖的深度遍歷。定義dfn[u]是結(jié)點u的時間戳，low[u]為u和u的子樹能夠追溯到的最早的棧中結(jié)點的時間戳。
??? low[u] = min{dfn[u], low[v](u,v為樹枝邊，u為v的父節(jié)點), dfn[v](u,v為指向棧中結(jié)點的后向邊)}；
??? 當dfn[u] == low[u]時，以u為根的搜索子樹上所有結(jié)點是一個強連通分量。
?
關于Tarjan算法的詳細介紹，參考:
http://hi.baidu.com/escorter2009/blog/item/f35951dc5bdb3de677c63826.html
?
POJ2186
題目大意：有n頭牛，每頭牛都希望自己受歡迎，輸入a b表示a認為b受歡迎。要求出受其它所有牛歡迎的牛的個數(shù)。
解：首先求強連通分量，分量中每頭牛都受分量中其它牛的歡迎。分量之間至多有一條有向邊。那么顯然需要找出出度為0的強連通分量，若有大于1的出度為0的強連通分量，這兩個連通分量互相不認為對方受歡迎，顯然個數(shù)為0；則有且僅有一個入讀度為0的強連通分量時，該強連通分量的結(jié)點數(shù)即為解。
Cpp代碼??
?? #include?<iostream>?? const?int?MAX?=?10002;?? int?n,m;?? int?low[MAX],dfn[MAX],seq;?? bool?inStack[MAX];?? struct?Edge?? {?? ????int?to;?? ????int?next;?? }e[50001];?? int?index[MAX],edgeNum;?? int?stack[MAX],top;?? int?belong[MAX];?????????????????????? int?outdegree[MAX];??? int?cnt;?????????????????????????????? ?? int?min(int?x,?int?y)?? {?? ????return?x?<?y???x?:?y;?? }?? ?? void?addEdge(int?from,?int?to)?? {?? ????e[edgeNum].to?=?to;?? ????e[edgeNum].next?=?index[from];?? ????index[from]?=?edgeNum++;?? }?? ?? void?Tarjan(int?u)?? {?? ????low[u]?=?dfn[u]?=?seq++;?? ????stack[top++]?=?u;????????????????????????? ????inStack[u]?=?true;?? ????for(int?i?=?index[u];?i?!=?-1;?i?=?e[i].next)?? ????{?? ????????int?w?=?e[i].to;?? ????????if(dfn[w]?<?0)?? ????????{?? ????????????Tarjan(w);?? ????????????low[u]?=?min(low[u],low[w]);?? ????????}?? ????????else?if(inStack[w])??????????????????? ????????????low[u]?=?min(low[u],dfn[w]);?? ????}?? ????if(dfn[u]?==?low[u])?????????????????? ????{?? ????????int?v;?? ????????cnt++;?? ?????????? ????????do?? ????????{?? ????????????top--;?? ????????????v?=?stack[top];?? ????????????inStack[v]?=?false;?? ????????????belong[v]?=?cnt;?? ????????}while(u?!=?v);?? ????}?? }?? ?? void?solve()?? {?? ????int?i,j;?? ????for(i?=?1;?i?<=?n;?i++)?? ????????if(dfn[i]?<?0)?? ????????????Tarjan(i);?? ????for(i?=?1;?i?<=?n;?i++)?? ????{?? ????????for(j?=?index[i];?j?!=?-1;?j?=?e[j].next)?? ????????{?? ????????????if(belong[i]?!=?belong[e[j].to])?? ????????????????outdegree[belong[i]]++;?? ????????}?? ????}?? ????int?num?=?0;?????? ????int?who;?????????? ????for(i?=?1;?i?<=?cnt;?i++)?? ????{?? ????????if(outdegree[i]?==?0)?? ????????{?? ????????????who?=?i;?? ????????????num++;?? ????????}?? ????}?? ????if(num?!=?1)?? ????????printf("0\n");?? ????else?? ????{?? ????????int?result?=?0;?? ????????for(i?=?1;?i?<=?n;?i++)?? ????????????if(belong[i]==who)?? ????????????????result++;?? ????????printf("%d\n",result);?? ????}?? }?? ?? int?main()?? {?? ????int?i,j;?? ????int?from,to;?? ????edgeNum?=?0;?? ????seq?=?0;?? ????top?=?0;?? ????cnt?=?0;?? ????memset(dfn,-1,sizeof(dfn));?? ????memset(index,-1,sizeof(index));?? ????memset(inStack,0,sizeof(inStack));?? ????memset(outdegree,0,sizeof(outdegree));?? ????scanf("%d?%d",&n,&m);?? ????for(i?=?0;?i?<?m;?i++)?? ????{?? ????????scanf("%d?%d",&from,&to);?? ????????addEdge(from,to);?? ????}?? ????solve();?? ????return?0;?? }??
?
POJ2553
題目大意：一個圖由結(jié)點集v和邊集E組成，現(xiàn)在要求出一個點集合：
??? bottom(G)={v∈V|?w∈V:(v→w)?(w→v)}(對于集合中的任意一點v和V中的任意一點w，如果v能到達w，那么w也能到達v)。
解：首先求強連通分量，聯(lián)想到出度為0的scc(因為出度不為0的scc，不滿足集合的定義)。
Cpp代碼??
?? #include?<iostream>?? const?int?MAX?=?5005;?? int?n,m;?? ?? struct?Edge?? {?? ????int?to;?? ????int?next;?? }e[MAX*MAX];?? int?index[MAX],edgeNum;?? ?? int?low[MAX],dfn[MAX],seq;?? int?stack[MAX],top;?? bool?inStack[MAX];?? int?belong[MAX],outdegree[MAX],cnt;?? int?result[MAX],count;?? ?? int?min(int?x,?int?y)?? {?? ????return?x?<?y???x?:?y;?? }?? ?? void?addEdge(int?from,?int?to)?? {?? ????e[edgeNum].to?=?to;?? ????e[edgeNum].next?=?index[from];?? ????index[from]?=?edgeNum++;?? }?? ?? void?Tarjan(int?u)?? {?? ????low[u]?=?dfn[u]?=?seq++;?? ????stack[top++]?=?u;?? ????inStack[u]?=?true;?? ????for(int?i?=?index[u];?i?!=?-1;?i?=?e[i].next)?? ????{?? ????????int?w?=?e[i].to;?? ????????if(dfn[w]?<?0)?? ????????{?? ????????????Tarjan(w);?? ????????????low[u]?=?min(low[u],low[w]);?? ????????}?? ????????else?if(inStack[w])??????????????????? ????????????low[u]?=?min(low[u],dfn[w]);?? ????}?? ????if(low[u]?==?dfn[u])?? ????{?? ????????int?v;?? ????????cnt++;?? ????????do?? ????????{?? ????????????top--;?? ????????????v?=?stack[top];?? ????????????inStack[v]?=?false;?? ????????????belong[v]?=?cnt;?? ????????}while(u?!=?v);?? ????}?? }?? ?? void?solve()?? {?? ????int?i,j;?? ????for(i?=?1;?i?<=?n;?i++)?? ????????if(dfn[i]?<?0)?? ????????????Tarjan(i);?? ????for(i?=?1;?i?<=?n;?i++)?? ????{?? ????????for(j?=?index[i];?j?!=?-1;?j?=?e[j].next)?? ????????{?? ????????????if(belong[i]?!=?belong[e[j].to])?? ????????????????outdegree[belong[i]]++;?? ????????}?? ????}?? ????for(i?=?1;?i?<=?n;?i++)?? ????{?? ????????if(outdegree[belong[i]]?==?0)?? ????????????result[count++]?=?i;?? ????}?? }?? ?? int?main()?? {?? ????int?i,j;?? ????int?from,to;?? ????while(true)?? ????{?? ????????scanf("%d",&n);?? ????????if(n==0)?? ????????????break;?? ????????edgeNum?=?top?=?seq?=?count?=?cnt?=0;?? ????????memset(dfn,-1,sizeof(dfn));?? ????????memset(index,-1,sizeof(index));?? ????????memset(inStack,0,sizeof(inStack));?? ????????memset(belong,0,sizeof(belong));?? ????????memset(outdegree,0,sizeof(outdegree));?? ????????scanf("%d",&m);?? ????????for(i?=?0;?i?<?m;?i++)?? ????????{?? ????????????scanf("%d?%d",&from,&to);?? ????????????addEdge(from,to);?? ????????}?? ????????solve();?? ????????if(count?==?0)?? ????????????printf("\n");?? ????????else?? ????????{?? ????????????for(i?=?0;?i?<?count-1;?i++)?? ????????????????printf("%d?",result[i]);?? ????????????printf("%d\n",result[i]);?? ????????}?? ????}?? ????return?0;?? } ?
總結(jié)
以上是生活随笔為你收集整理的有向图——强连通分量的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
