dfs后，如果 low[v] >= dfn[u]，则 u 就是割点。
不过如果 u 是搜索树的根节点的话，还要判断他至少有两个出边，而且这个判断必须加在v没有被走到的前提下。这样就表示有一些点只能通过根节点走到，那么如果这种点多于1个的话，根节点就是割点了。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 1e5 + 5; 20 inline ll read() 21 { 22 ll ans = 0; 23 char ch = getchar(), last = ' '; 24 while(!isdigit(ch)) {last = ch; ch = getchar();} 25 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 26 if(last == '-') ans = -ans; 27 return ans; 28 } 29 inline void write(ll x) 30 { 31 if(x < 0) x = -x, putchar('-'); 32 if(x >= 10) write(x / 10); 33 putchar(x % 10 + '0'); 34 } 35 36 int n, m; 37 vector<int> v[maxn]; 38 39 int dfn[maxn], low[maxn], cnt = 0; 40 bool cut[maxn]; 41 int root, ccnt = 0; 42 void tarjan(int now) 43 { 44 dfn[now] = low[now] = ++cnt; 45 int flg = 0; 46 for(int i = 0; i < (int)v[now].size(); ++i) 47 { 48 if(!dfn[v[now][i]]) 49 { 50 tarjan(v[now][i]); 51 low[now] = min(low[now], low[v[now][i]]); 52 if(low[v[now][i]] >= dfn[now]) 53 { 54 flg++; 55 if(now != root || flg > 1) 56 { 57 if(!cut[now]) ccnt++; 58 cut[now] = 1; 59 } 60 } 61 } 62 else low[now] = min(low[now], dfn[v[now][i]]); 63 } 64 65 } 66 67 int main() 68 { 69 n = read(); m = read(); 70 for(int i = 1; i <= m; ++i) 71 { 72 int x = read(), y = read(); 73 if(x == y) continue; 74 v[x].push_back(y); v[y].push_back(x); 75 } 76 for(int i = 1; i <= n; ++i) if(!dfn[i]) root = i, tarjan(i); 77 write(ccnt); enter; 78 for(int i = 1; i <= n; ++i) if(cut[i]) write(i), space; enter; 79 return 0; 80 }