思路
很好,这又是一道模板。
求割点的tarjan和求强连通分量的tarjan原理相同,但是实际写法并不完全相同。要注意的是,对于一个点u,它在不同情况下要满足以下两个条件才能称之为割点:
(1)low[v]>=dfn[u](v是u在搜索树上的儿子,且u不在环中)
(2)u在搜索树上有两个以上的儿子(u在环中)
那么这需要怎么维护呢?我们只需要在搜索的过程中记当前点的祖先即可。若它在搜索过程中找到了自己,那说明在环中,就必须要满足上述(2)的条件才行。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 20010
#define MAXM 100010
int n, m, idx, cnt;
int dfn[MAXN], low[MAXN];
int res, cutp[MAXN];
class node{
public:
int to;
node *nxt = NULL;
} edge[MAXM << 1], *head[MAXN];
inline int read(void){
int f = 1, x = 0;char ch;
do{ch = getchar();if(ch=='-')f = -1;} while (ch < '0' || ch > '9');
do{ x = (x << 1) + (x << 3) + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
return f * x;
}
inline int _min(int x, int y) { return x < y ? x : y; }
inline void add_edge(int x,int y){
++cnt;
edge[cnt].nxt = head[x];
head[x] = &edge[cnt];
head[x]->to = y;
return;
}
void tarjan(int k,int fa){
dfn[k] = low[k] = ++idx;
int kid = 0;
for (node *i = head[k]; i != NULL; i = i->nxt){
int v = i->to;
if(!dfn[v]){
tarjan(v,fa);
low[k] = _min(low[k], low[v]);
if(low[v]>=dfn[k]&&k!=fa) cutp[k] = 1;
if(k==fa)++kid;
}
low[k] = _min(low[k], dfn[v]);
}
if(kid>=2&&k==fa) cutp[k] = 1;
return;
}
int main(){
n = read(), m = read();
for (int i = 1; i <= m; ++i){
int u = read(), v = read();
add_edge(u, v), add_edge(v, u);
}
for (int i = 1; i <= n; ++i)
if(!dfn[i])tarjan(i,i);
// for (int i = 1; i <= n;++i)
// printf("dfn[%d]=%d,low[%d]=%d\n", i, dfn[i], i, low[i]);
for (int i = 1; i <= n; ++i)
if (cutp[i]) ++res;
printf("%d\n", res);
for (int i = 1; i <= n; ++i)
if(cutp[i])printf("%d ", i);
return 0;