割点（关节点）（GRL_3_A:Articulation Point）

在联通图G中，如果删除顶点u以及从u出发的所有边后所得的子图不连通，我们就称u为图G的关节点（Articulation Point）或者连接点。

把深度优先搜索加以利用。

在一次深度优先搜索中找出以下变量值，prenum[u]，parent[u]，lowest[u]。

prenum[u]：以G的任意顶点作为起点进行DFS，将各个顶点u的访问(发现)顺序记录在prenum[u]中。

parent[u]：通过DFS生成一棵树（DFS tree），将其中结点u的父节点记录在parent[u]中。这里DFS tree记作T。

lowest[u]：对于个顶点u，计算下列情况中的最小值并计入lowest[u]

1.prenum[u]

2.T内顶点u的所有子节点x的lowest[x].

3.存在G的Backedge(u,v)时，顶点v的prenum[v]（Backedge（u，v））表示图G内“从顶点u出发指向T内的顶点v”且“不属于T"的边.

有了这些变量，我们便可以通过下列这些方法确定关节点。

1.T的根节点r拥有2个以上子节点时（充分必要条件），r为关节点

2.对于各顶点u，设u的父节点parent[u]为p，如果prenum[p]<=lowest[u]（充分必要条件），则p为关节点（p为根节点套用1）.这表明顶点u及u在T中的子孙均不具备与p祖先相连的边。

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>

using namespace std;

const int maxn=1e5+5;

int n,m,prenum[maxn],lowest[maxn],parent[maxn],timer;
bool visited[maxn];
vector<vector<int> >g(maxn);

void dfs(int current,int prev)
{
    prenum[current]=lowest[current]=timer;
    timer++;
    visited[current]=true;
    int next;
    for(int i=0;i<g[current].size();i++){
        next=g[current][i];
        if(!visited[next]){
            parent[next]=current;
            dfs(next,current);
            lowest[current]=min(lowest[current],lowest[next]);
        }else if(next!=prev){
            lowest[current]=min(lowest[current],prenum[next]);
        }
    }
}

void art_point()
{
    for(int i=0;i<n;i++){
        visited[i]=false;
    }
    timer=1;
    dfs(0,-1);
    set<int>s;
    int np=0;
    for(int i=1;i<n;i++){
        int p=parent[i];
        if(p==0){
            np++;
        }else{
            if(prenum[p]<=lowest[i]){
                s.insert(p);
            }
        }
    }
    for(set<int>::iterator it=s.begin();it!=s.end();it++){
        cout<<*it<<endl;
    }
    if(s.empty()){
       printf("no\n");
    }

}

int main()
{
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    art_point();
    return 0;
}