http://2014.sprout.csie.org/oj/pro/183/
找割點。
這題是無向圖找割點，找割點要運用到 tarjan algorithm。
割點的定義是在一個連通圖中，只要拿掉該點，就會有點變成不連通，就稱該點為割點(如果點換成邊稱為橋)。
具體方法是，維護一個low函數，代表一個點不經過DFS樹(你走訪的路徑)上的路徑，可以走到的編號最小的點。先將邊分成 樹邊(DFS樹上的邊)，前向邊(連到編號比自己大的點的邊)，向後邊(反之)，其他還有幾種，這題用不到。
DFS，並在進入該點時，賦予該點一個DFS編號(一個不斷增加的全域變數，代表DFS走過所有點的順序)，之後，如果遇到向後邊(一個邊連到一個走過的點，住意要排除該點的父節點)，就將自己的low函數更新成兩個點中比較小的那個。這樣就可以得到一個正確的low函數。
一個點是不是割點，只要他的任意子節點的low函數大於等於自己的DFS編號(他小孩最高只走的到他)，那把這個點拔掉，他小孩就走不到祖先了，所以他就是割點。
要注意在判斷是不是割點時，要確定那是他小孩，不是他孫子，也就是那條邊是樹邊，不是前向邊。不然，會有意外狀況發生喔!!
還有就是，以上判斷對根節點沒有用，根節點要特判，如果根節點有兩顆以上子樹(DFS沒路了才會回根節點換路走)，根就是割點。
注意這題題目給的圖不連通，所以題目是在一堆圖上分別找該圖的割點。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #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;
system("pause");
return 0;
}
|
