我们在做dfs的时候，当访问到一个节点时，会出现四种情况：

1.此节点未被访问过，则此次的访问关系边（发起点——>接受点）称为树边（tree edge）；(未进栈节点)

2.此节点被访问过但此节点的子孙还没访问完，换句话说，此次的发起点的源头可以追溯到接收点，则此次访问关系边称为后向边（back edge）（栈中节点）；

3.此节点被访问过且此节点的子孙已经访问完，而且发起点是搜索初始边，则称为前向边（down edge）（出栈节点）；

4.此节点被访问过且此节点的子孙已经访问完，而且发起点不是搜索初始边，则称为交叉边（cross edge）（出栈节点）。

其实这种分类只是相对的，也会随着dfs的改变而改变，比如搜索入口、搜索顺序等。（其中，在无向图中，交叉边不存在，想一想，为什么）

从一到题说起：

所谓割点，就是一个连通无向图中，删除某一点和与它连接的所有的边后，剩下的点不再连通，则这个点是关节点。

题目：给定无向图的点数（N），边数（M），以及M条边，输出图的所有关节点，以由到大输。

N<=100000，M<=300000

样例：

输入：

10 17

2 1

2 6

2 8

3 2

3 5

4 2

4 7

5 3

5 4

6 3

7 1

7 2

7 3

7 5

8 2

9 6

10 8

输出：

3

2 6 8 

样例第一行为N和M，接下来M行为M条边。输出第一行为割点个数，接下来由小到大输出割点的编号。

一看到这道题，就想，把任意一个点给去掉，然后遍历一次，看是否位连通图，如果不是，就是割点。

但是这样的复杂度是O(n(n+m))严重超时

好吧，我们务必要钻研出dfs的特性，使之在线性时间，即O(n+m)时间内求出割点

第一我们知道在遍历时一定会出现割点吧，这不是废话吗

然后我们想根节点的成为割点的条件，必须是有＞2个儿子节点才可以吧(*^▽^*)

然后，就是在搜索时，怎么判断一个点就是割点呢

定理：在无向图的连通图G中，当且仅当一个点u存在一个可遍历的后代节点v无法连回一个比u更老的节点时，这个点u就一个割点

证明：考虑u的任意子节点v。如果v及其还带无法找到一个更老的节点，那么无论如何都无法连回去，反过来，如果存在，那么就一定可以通过那个连回去的点继续连通，则u不是割点。

证毕。

有人说，有可能从当前点连回一个已经出栈的点，不可能，为什么：因为一旦出栈，那么说明他可以搜到的节点已经搜毕。因为这是无向图，那么这个点一定不会连到一个出栈的点上去。

完啦。

#include
     
      #include
      
       #include
       
        #define N 100000+10using namespace std;int head[N],num;struct edge{    int next,to;};edge e[2*N*(N-1)];void add(int from,int to){    e[++num].next=head[from];    e[num].to=to;    head[from]=num;}int flag[N],dfn[N],low[N];int tim=0,tot;int root;void dfs(int u,int fa){    //vis[u]=1;    tim++;    low[u]=dfn[u]=tim;    int son=0;    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        //if(v==fa)continue;        if(!dfn[v])        {            son++;            dfs(v,u);            low[u]=min(low[u],low[v]);            if(u!=root&&low[v]>=dfn[u])                flag[u]=1;            if(u==root&&son>=2)                flag[u]=1;            }        else if(v!=fa)        {            low[u]=min(low[u],dfn[v]);        }    }    return;}int main(){    int n,m;    scanf("%d%d",&n,&m);    int x,y;    for(int i=1;i<=m;i++)    {        scanf("%d%d",&x,&y);        add(x,y);        add(y,x);    }    root=1;    dfs(1,root);    int cnt=0;    for(int i=1;i<=n;i++)    {        if(vis[i]==1)cnt++;        //printf("%d ",i);    }    printf("%d\n",cnt);    for(int i=1;i<=n;i++)    {        if(flag[i]==1)printf("%d ",i);    }    return 0;}