输入格式

第一行输入两个正整数 n,mn,m。

下面 mm 行每行输入两个正整数 x,yx,y 表示 xx 到 yy 有一条边。

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

输入输出样例

输入 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
输出 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
1 
5

 

 

CODE

#include  < bits/stdc++.h >
#define  dbg ( x ) cout  << #x  <<  " = "  << x  << endl

using  namespace  std ;
typedef  long  long LL ;
const  int maxn  =  1e5  +  7 ;

int head [maxn ], dfn [maxn ], low [maxn ];
int cnt  =  0 , tot  =  0 , tim  =  0 , top  =  1 , cl  =  0 , k ;
int vis [maxn ];
int color [maxn ];
int iscut [maxn ];
int tott , n , m ;

/*
head[],结构体edge:存边

dfn[],low[]:tarjan中数组

st[]:模拟栈

out[]:出边

sd[]:强连通分量存储

dq[]:统计答案
*/

template < class  T > inline  void  read ( T  & res )
{
     char c ;T flag = 1 ;
     while ((c = getchar ()) < ' 0 ' ||c > ' 9 ' ) if (c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
     while ((c = getchar ()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}

struct  Edge {
     int nxt , to ;
} edge [maxn  *  2 ];

inline  void  BuildGraph ( int  from ,  int  to )
{
    cnt ++ ;
    edge [cnt ].to  = to ;
    edge [cnt ].nxt  = head [from ];
    head [from ]  = cnt ;
}

stack <int> s ;

void  tarjan ( int  u ,  int  fa )
{
     int son  =  0 ;
    s . push (u );
    low [u ]  = dfn [u ]  =  ++tim ;
     for  (  int i  = head [u ]; i ; i  = edge [i ].nxt  )  {
         int v  =  edge [i ]. to ;
         if ( ! dfn [v ])  {
             tarjan (v , fa );
             low [u ]  =  min ( low [u ],  low [v ]);
             if ( low [v ]  >=  dfn [u ]  && u  != fa )  {
                 iscut [u ]  =  1 ;
             }
             if (u  == fa )  {
                 ++son ;
             }
         }
         low [u ]  =  min ( low [u ],  dfn [v ]);
     }
     if (son  >=  2  && u  == fa )  {
         iscut [ 1 ]  =  1 ;
     }
}

void  init ()  {
    cnt  =  0 ;
    cl  =  0 ;
    tim  =  0 ;
    k  =  0 ;
     while ( !s . empty ())  {
         s . pop ();
     }
    
     memset (vis ,  0 ,  sizeof (vis ));
     memset (dfn ,  0 ,  sizeof (dfn ));
     memset (low ,  0 ,  sizeof (low ));
     memset (iscut ,  0 ,  sizeof (iscut ));
     memset (edge ,  0 ,  sizeof (edge ));
     memset (head ,  0 ,  sizeof (head ));
}

int  main () 
{
     init ();
     scanf ( "%d  %d " , &n ,  &m );
     for  (  int i  =  1 ; i  <= m ;  ++i  )  {
         int x , y ;
         scanf ( "%d  %d " , &x ,  &y );
         BuildGraph (x , y );
         BuildGraph (y , x );
        
     }
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         if ( ! dfn [i ])  {
             tarjan (i , i );
         }
     }
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         if ( iscut [i ])  {
             ++tott ;
         }
     }
     printf ( "%d \n" ,tott );
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         if ( iscut [i ])  {
             printf ( "%d   " ,i );
         }
     }
     return  0 ;
}