割点用类似tarjan的算法求出最早遍历的祖先然后维护即可。注意要特判root，这点很重要。
然后如果要求分割的分量，那么就是这个节点对他的子树是割点的数目+1。sigh。。root要特判。。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ' '; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }
const int N=2005;
int ihead[N], cnt, rt, iscut[N], FF[N], LL[N], fa[N], tot;
struct ED { int to, next; }e[N*N];
void add(int u, int v) {
e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;
e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;
}
void tarjan(int u, int fa) {
FF[u]=LL[u]=++tot;
int child=0;
for(int i=ihead[u]; i; i=e[i].next) {
int v=e[i].to;
if(!FF[v]) {
tarjan(v, u);
++child;
if(LL[v]>=FF[u]) ++iscut[u]; //dbg(iscut[u]); dbg(u);
LL[u]=min(LL[v], LL[u]);
}
else if(FF[v]<FF[u] && fa!=v) LL[u]=min(LL[u], FF[v]);
}
if(child==1 && fa==-1) iscut[u]=0;
else if(child>1 && fa==-1) iscut[u]=child-1;
}
int main() {
int u, v, cs=0;
while(1) {
u=getint(); if(u==0) break;
v=getint();
CC(ihead, 0); CC(iscut, 0); cnt=tot=0; CC(FF, 0); CC(LL, 0);
++cs;
add(u, v); rt=max(rt, v);
while(1) {
u=getint(); if(u==0) break;
v=getint();
add(u, v); rt=max(rt, v);
}
for1(i, 1, rt) if(ihead[i] && !FF[i]) tarjan(i, -1);
// for1(i, 1, rt) if(hav[i] && iscut[i]) printf("%d
", i);
int flag=0;
printf("Network #%d
", cs);
for1(i, 1, rt) if(iscut[i]) printf(" SPF node %d leaves %d subnets
", i, iscut[i]+1), flag=1;
if(!flag) puts(" No SPF nodes");
puts("");
}
return 0;
}
用邻接矩阵写的。自己慢慢理解吧
#include <iostream>
#include <cstring>
using namespace std;
#define CC(c) memset(c, 0, sizeof(c))
const int maxn=5000;
int iscut[maxn], g[maxn][maxn], low[maxn], pre[maxn], _pre, n, m;
int dfs(int u, int fa) {
low[u]=pre[u]=++_pre; //初始时
int child=0; //如果child=1并且它是根，就不是割顶
for(int v=1; v<=n; ++v) if(g[u][v]) {
if(!pre[v]) {
child++;
int lowv=dfs(v, u); //找子女的最小low，看是否能回溯到自己的fa前面
if(lowv<low[u]) low[u]=lowv; //更新最小
if(lowv>=pre[u]) iscut[u]=1; //如果在fa后面，即没有指向fa前面，就是一个割顶
}
else if(pre[v]<pre[u] && v!=fa && low[u]>pre[v])
//因为是无向图，所以要判断是否是之前的访问的第二次访问回去的环
low[u]=pre[v];
}
if(fa<0 && child==1) iscut[u]=0;
return low[u];
}
void find_cut() {
CC(iscut); CC(low); CC(pre);
for(int i=1; i<=n; ++i) if(!pre[i]) dfs(i, -1);
for(int i=1; i<=n; ++i) if(iscut[i]) cout << i << " ";
cout << endl;
}
int main() {
cin >> n >> m;
for(int i=1; i<=n; ++i) {
int a, b;
cin >> a >> b;
g[a][b]=g[b][a]=1;
}
find_cut();
return 0;
}