```cpp
#include <bits/stdc++.h>
#define MAXN 100001*2
using namespace std; //iscut数组记录是否为割顶 ,low数组记录每个点能连通点时间戳的最小值
int pre[MAXN],low[MAXN],iscut[MAXN],dfs_clock = 0;//pre数组记录操作前时间戳
int head[MAXN],next[MAXN],point[MAXN],total = 0;
void link(int x,int y){
total ++;
next[total] = head[x];
head[x] = total;
point[total] = y;
}
int dfs(int u,int fa){
int lowu = pre[u] = ++dfs_clock; //给每个点打时间戳
int child = 0; // 为判断根是否为割顶
for(int j = head[u]; j != 0; j=next[j]){
int v = point[j];
if(!pre[v]){ // 如果后代没有走过,也就是说不是2次遍历或者反向边,那么往下搜索
child ++;
dfs(v, u);
lowu = min(lowu, low[v]); // 从后代中更新能连通的最小时间戳的点
if(low[v] >= pre[u]) // 如果没有与祖先连通就说明是割顶
iscut[u] = 1;
}
else if(fa != v && pre[v] < pre[u]) // 从反向边更新最小时间戳
lowu = min(lowu , pre[v]);
}
if(fa < 0 && child == 1) // 判断根节点是否是割顶
iscut[u] = 0;
low[u] = lowu;
}
int main(){
int m, n;
ios::sync_with_stdio(0);
memset(pre,0,sizeof(pre));
cin>>n>>m;
for(int i = 1;i <= m;i ++){
int x, y;
cin >> x >> y;
link(x, y);
link(y, x);
}
dfs(1 , -1);
int ans = 0;
for(int i = 1;i <= n; i++)
if(iscut[i]==1)
ans++;
cout<<ans<< endl;
for(int i = 1;i <= n; i++)
if(iscut[i]==1)
cout<<i<<" ";
return 0;
}
```
by xw001 @ 2017-10-21 22:23:48
去掉了某个割顶,图是不连通了,但A和B还是有可能在同一个联通块里啊
by sjkmost @ 2017-10-21 22:55:40
@[sjkmost](/space/show?uid=30043) 嗷嗷嗷,是酱紫啊 ,我又没动脑子 了,感谢大佬指点
by xw001 @ 2017-10-21 23:18:16
@[xw001](/user/15044) 支配点与支配边的题目
by damocris @ 2021-10-29 14:43:00
@[damocris](/user/119884) 太久了,高中写的东西,现在大学都快毕业了
by xw001 @ 2022-03-09 20:38:05