割点——tarjan
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int MAXN = 20001; 5 const int MAXM = 100001; 6 int n, m; 7 int ans;//个数 8 9 10 int head[MAXN], cnt, v[2 * MAXM], nxt[2 * MAXM]; 11 void add(int x, int y) { 12 nxt[++cnt] = head[x]; 13 head[x] = cnt; 14 v[cnt] = y; 15 } 16 17 18 int dfn[MAXN], low[MAXN], ind; 19 int cut[MAXN]; 20 21 22 void tarjan(int now, int fa) { 23 dfn[now] = low[now] = ++ind; 24 int child = 0; 25 for (int i = head[now]; i ; i = nxt[i]) { 26 if(!dfn[v[i]]) { 27 tarjan(v[i], now); 28 low[now] = min(low[now], low[v[i]]); 29 30 if(low[v[i]] >= dfn[now] && now != fa) cut[now] = 1;//不为根节点 31 if(now == fa) child++; //为根节点,子树统计 32 } 33 else { 34 low[now] = min(low[now], dfn[v[i]]); 35 } 36 } 37 if(now == fa && child >= 2) cut[now] = 1;//为根节点且有两个及以上的子节点 38 } 39 int main() { 40 41 scanf("%d%d", &n, &m); 42 for (int i = 1; i <= m; i++) { 43 int x, y; 44 scanf("%d%d", &x, &y); 45 add(x, y); 46 add(y, x); 47 } 48 49 for (int i = 1; i <= n; i++) 50 if(!dfn[i]) 51 tarjan(i, i); 52 53 for (int i = 1; i <= n; i++) 54 if(cut[i] == 1) 55 ans++; 56 printf("%d\n", ans); 57 for (int i = 1; i <= n; i++) 58 if(cut[i] == 1) 59 printf("%d ", i); 60 61 62 return 0; 63 }