图的连通性以及割点
首先明白幾個定理：
- 連通分量：無向圖?G?的一個極大連通子圖稱為?G?的一個連通分量（或連通分支）。連通圖只有一個連通分量，即其自身；非連通的無向圖有多個連通分量。
- 強連通圖：有向圖?G=(V,E) 中，若對于V中任意兩個不同的頂點?x?和?y?，都存在從x?到?y?以及從?y?到?x?的路徑，則稱?G?是強連通圖(Strongly Connected Graph)。相應地有強連通分量(Strongly Connected Component)的概念。強連通圖只有一個強連通分量，即是其自身；非強連通的有向圖有多個強連通分量
1. 判斷無向圖的連通性。
? ?用bfs或者dfs，遍歷，如果能遍歷完所有結點，則是連通圖。
? 比如，要求無向圖的割點的集合，最容易想到的方法就是依次測試每個結點判斷其對圖連通性的影響。
??有更簡單的方法。
2. 有向圖的單連通性。對于任意的兩個點，i,j，存在i到j或者j到i的路徑
??1. 最容易想到的算法是floyd算法。
?? ? ?floyd算法本來用以求圖中任意兩點間的最短路徑，大體思路是：
?? ? 依次以每個點k作為i--->j的中間節點，求d(i,j) = min(d(i,j),d(i,k)+d(k,j))
?? ?如果用floyd算法判斷任意兩個點的連通性？
?? ?可以直接用上面的算法，但是可以將加法和min操作轉為位運算。
?? ?d(i,j) = d(i,j) | (d(i,k) & d(k,j))
?2. 上面的算法時間復雜度是O(n^3)
?? ??http://hi.baidu.com/735612658gfy/item/e2e8c8d3362fa9f2b3f7777b
???
思路：判斷一個有向圖是不是強連通的可以直接用tarjan算法。
? ? ? ? ? 但是判斷是不是單向聯通的就麻煩了。
? ? ? ? ? 開始我想用floyd，后來又想到了一條路一條路的找，但是這兩種方法的復雜度太高。
正解：對于一個DAG圖，若是單向聯通的我們可以有這么一個性質，就是存在一條路，這條路可以經過圖中的每一個點。下面證明一下。
我們從圖中選擇一個入度為0的點a，和一個出度為0的點b，則剩下的點肯定都滿足在a，b之間。
不妨找一點k ，則a~k~b，剩下的點也肯定在兩個~之間的一個，以此類推。
我們先讓這張圖變成DAG，我們用tarjan算法縮點，這張圖就變成了一個DAG圖。
#include<cstdio> #include<iostream> #include<cstring> #include<stack> using namespace std; stack<int>s; struct hh{int u,v,next;}tp[6005],map[6006];int head[1050],mhead[1050],num,mnum,low[1050],lp[1050],now,f[1050];bool in[1050];int n,m,step,total;void add(int a,int b){tp[num].u=a;tp[num].v=b;tp[num].next=head[a]; head[a]=num++;}void madd(int a,int b){map[mnum].u=a; map[mnum].v=b;map[mnum].next=mhead[a]; mhead[a]=mnum++;}void init(){int a,b;num=0; mnum=0;step=total=1;while(!s.empty()) s.pop();for(int i=1;i<=n;i++){in[i]=0;low[i]=lp[i]=f[i]=0;}memset(head,-1,sizeof(head));memset(mhead,-1,sizeof(mhead));scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d",&a,&b);add(a,b);}}void tarjan(int u){int v;low[u]=lp[u]=step++;s.push(u); in[u]=1;for(int i=head[u];i!=-1;i=tp[i].next){v=tp[i].v;if(!low[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(in[v]){low[u]=min(low[u],lp[v]);}}if(low[u]==lp[u]){int haha;while(1){haha=s.top(); s.pop();f[haha]=total; in[haha]=0;if(haha==u)break;}total++;}}void suodian(){for(int i=0;i<num;i++){if(f[tp[i].u]!=f[tp[i].v])madd(f[tp[i].u],f[tp[i].v]);}}bool can[1004][1004];int b[1050];bool dfs(int u,int now){in[u]=1;if(now==total-1)return true;bool flag=0;for(int i=mhead[u];i!=-1;i=map[i].next){flag=dfs(map[i].v,now+1);if(flag)return true;}return false ;}void result(){memset(in,0,sizeof(in));for(int i=1;i<=n;i++){if(!in[i]){bool flag=dfs(i,1);{if(flag){cout<<"Yes"<<endl; return ;}}}}cout<<"No"<<endl;}int main(){int t;scanf("%d",&t);while(t--){init();for(int i=1;i<=n;i++)if(!low[i])tarjan(i);suodian();//重新建圖result();}}
也可以用上面的算法求出有向圖的單連通分支， 對入度為0點,遞歸搜尋各向前通路至每一不可再前行點時，可對應得出一單項連通分支
總結
