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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
|
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1e4+10, M = 1e5+10; struct { int v, next; } e[M<<1]; int low[M], que[M], cnt, head[M], stack[M], top, indexx, dfn[M]; bool cut[M]; bool instack[M]; void add(int u,int v) { e[++cnt].next = head[u]; e[cnt].v = v; head[u] = cnt; } void tarjan(int x,int pre) { int child = 0; low[x] = dfn[x] = ++indexx; stack[++top]=x; instack[x]=1; for (int i = head[x]; i;i=e[i].next) { int v = e[i].v; if(!dfn[v]) { tarjan(v, x); low[x] = min(low[x], low[v]); if(x!=pre&&dfn[x]<=low[v]) cut[x] = 1; if(x==pre) child++; } else if(instack[v]) low[x] = min(low[x], dfn[v]); } if(child>1&&x==pre) cut[x] = 1; }
void init() { memset(head, 0, sizeof head); } int main() { init(); int n, m; cin >> n >> m; for (int i = 1; i <= m;i++) { int a, b; cin >> a >> b; add(a, b), add(b, a); } for(int i = 1;i <= n;i++) { if(!dfn[i]) tarjan(i,i); } int ans = 0; for(int i = 1;i <= n;i++) ans += cut[i]; printf("%dn",ans); for(int i = 1;i <= n;i++) { if(cut[i]) printf("%d ",i); } return 0; }
|
近期评论