方法一：并查集
init_set(|V|);for each(u,v) in E union(u,v);//條件find(a)=find(b),說明a,b同屬于一個連通分量方法二：深搜
dfs(u){ vis[u]=eis; for each (u,v) in E if(!vis[v]) dfs(v);}memset(vis,0,sizeof(vis));eid=0;for each v in V{ if(!vis[v]) { ++eid; dfs(v); }}去掉邊的方向以后形成的無向圖是連通圖，沒有孤立點 算法：把有向邊看作無向邊，用并查集或深搜
Tarjan算法
void tarjan(int u){ vis[u]=true; dfn[u]=low[u]=++Time; stack.push(u); for each (u,v) in E if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if(ins[v]) //只有回邊才更新low值，過濾掉橫跨邊 low[u]=min(low[u],dfn[v]); end for if(low[u]>=dfn[u])//low[u]是否受過回邊牽連 { do { v=stack.pop(); PRint v; }while(u!=v);//打印一組強連通的頂點集 }}（1）拓撲排序
bool toposort(int n,int *que){ int i,j,v; static int deg[MAXN],stk[MAXN],top,sz; memset(deg,0,sizeof(deg)); for(int i=0;i<n;i++) { for(int j=p[i],~j;j=e[j].next)//枚舉i的鄰邊 { v=e[j].v; deg[v]++; } } for(top=i=0;i<n;i++) { if(!deg[i]) stk[top++]=i; } sz=0; while(top) { v=stk[--top]; que[sz++]=v; for(int i=p[v];~i;i=e[i].next) { v=e[i].v; --deg[v]; if(!deg[v]) stk[top++]=v; } } return (sz==n);//返回是否無環}（2）用強連通分量來做，尋找圖的強連通子圖 （3）用改進的DFS解決問題
//C[N]的值//0:此結點沒有被訪問過//-1:此結點被訪問過至少1次，其后代結點正在被訪問//1:其后代結點都被訪問過void dfs(u){ C[u]=-1;//回邊的標志 for each(u,v) in E if(!C[v]) dfs(v); else if(C[v]==-1)//回邊，存在環 circle_found(); C[u]=1;//橫跨邊、前向邊的標志}性質： （1）邊連通分量不含橋，含有橋的子圖不是邊連通分量 （2）任何一個無向連通圖都恰好由橋和邊連通分量組成 （3）如果將每個邊連通分量縮成一個點，那么新圖必然是一棵樹，每一條樹邊在原圖就是一個橋 算法： 定義low[u]的值為搜索樹中u的樹邊、回邊、前向邊的關聯結點中low的最小值，設v是一個樹邊的關聯結點，那么low[u]比low[v]大是說明u-v是一個橋，復雜度為O(|E|)
void edge_conn(fa,u){ vis[u]=true; dfn[u]=low[u]=++Time; stack.push(u); for each (u,v) in E if not vis[v] then edge_conn(u,v); low[u]=min(low[u],low[v]); if low[v]>dfn[u] then //說明深搜樹中，(u,v)是樹邊 print(u,v) //v的子樹沒有越過u的回邊，可見(u,v)是橋 do { v=stack.pop(); print v; }while(u!=v);//記錄一個邊連通分量 end if else if u!=fa and low[v]<low[u] low[u]=dfn[v]; end for}性質：雙連通分量不含割點，含有割點的子圖不是雙連通分量，但可能是邊連通量。 |連通分量|>|邊連通分量|>|雙連通分量| 算法：
dfs(fa,u){ int i; dfn[u]=low[u]=++Time; vis[u]=true; for each (u,v) in E if(v==fa) continue; if vis[i] then low[u]=min(low[u],dfn[v]); else dfs(u,v); low[v]=min(low[u],low[v]); if(low[v]>=dfn[u]) cut[u]++; //cut[u]表示點u的存在與否導致的連通分量的變化數目 end if end for if(fa!=-1) cut[u]++;}新聞熱點
疑難解答
