轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年6月1日 星期日

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;
}