TOJ::183 / 高棕櫚傳遞鏈

http://2014.sprout.csie.org/oj/pro/183/
找割點。

這題是無向圖找割點，找割點要運用到 tarjan algorithm。

割點的定義是在一個連通圖中，只要拿掉該點，就會有點變成不連通，就稱該點為割點(如果點換成邊稱為橋)。

具體方法是，維護一個low函數，代表一個點不經過DFS樹(你走訪的路徑)上的路徑，可以走到的編號最小的點。先將邊分成 樹邊(DFS樹上的邊)，前向邊(連到編號比自己大的點的邊)，向後邊(反之)，其他還有幾種，這題用不到。

DFS，並在進入該點時，賦予該點一個DFS編號(一個不斷增加的全域變數，代表DFS走過所有點的順序)，之後，如果遇到向後邊(一個邊連到一個走過的點，住意要排除該點的父節點)，就將自己的low函數更新成兩個點中比較小的那個。這樣就可以得到一個正確的low函數。

一個點是不是割點，只要他的任意子節點的low函數大於等於自己的DFS編號(他小孩最高只走的到他)，那把這個點拔掉，他小孩就走不到祖先了，所以他就是割點。

要注意在判斷是不是割點時，要確定那是他小孩，不是他孫子，也就是那條邊是樹邊，不是前向邊。不然，會有意外狀況發生喔!!

還有就是，以上判斷對根節點沒有用，根節點要特判，如果根節點有兩顆以上子樹(DFS沒路了才會回根節點換路走)，根就是割點。

注意這題題目給的圖不連通，所以題目是在一堆圖上分別找該圖的割點。

#include <cstdlib>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 1000001
#define LL long long
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
int low[N],dfs[N],dfst,root,roott;
bool wed[N],IF[N];
vector<int> D[N];
void DFS(int now,int no){
    wed[now]=true;
    low[now]=dfs[now]=dfst++;
    F(D[now].size()){
        if(now==root&&!wed[D[now][i]])roott++;
        if(!wed[D[now][i]]){
            DFS(D[now][i],now);
            if(dfs[now]<=low[D[now][i]]&&now!=root)IF[now]=true;
        }
        if(D[now][i]!=no)low[now]=min(low[now],low[D[now][i]]);
    }
}
int main(int argc,char *argv[])
{
    ios_base::sync_with_stdio(false);
    int n,m,a,b;
    cin>>n>>m;
    F(m){
        cin>>a>>b;
        D[a].push_back(b);
        D[b].push_back(a);
    }
    F(n){
        if(!wed[i+1]){
            root=i+1;
            roott=0;
            DFS(i+1,i+1);
            if(roott>1)IF[root]=true;
        }
    }
    F(n)if(IF[i+1])cout<<i+1<<endl;
    //F(n)cout<<low[i+1];cout<<endl;
    system("pause");
    return 0;
}