割点 get ！

A4paper · 2018-09-16 17:31:28 · 个人记录

用 tarjan 算法找割点，

遍历 dfs 树，如果有返祖边，那么当前点一定不是割点，

反过来，如果：

DFN [ u ] <= LOW [ v ] 时，点 u 即是割点

当然，对于 root 要特判，如果 root 有两棵及以上的子树，

那 root 即是割点。

模板：

传送门

int n,m,cnt,root,rootson,tot;
int head[MAXN];
int cut[MAXN],LOW[MAXN],DFN[MAXN],vis[MAXN];

struct node{
    int to,next;
}map[MAXN];

void add(int u, int v)
{
    map[++cnt] = (node){v,head[u]};
    head[u] = cnt;
}

void tarjan(int u, int fa)
{
    DFN[u] = LOW[u] = ++cnt;
    vis[u] = 1;
    for(int k=head[u];k;k=map[k].next)
    {
        int v = map[k].to;
        if(!vis[v])
        {
            tarjan(v,u);
            LOW[u] = min(LOW[u],LOW[v]);
            if(u!=root && DFN[u]<=LOW[v])   cut[u] = 1; else
            if(u==root && ++rootson==2)     cut[u] = 1;
        }
        else if(v != fa)    LOW[u] = min(LOW[u],DFN[v]);
    }
}

int main(void)
{
    cin >> n >> m;
    for(int i=1,u,v;i<=m;i++)
    {
        cin >> u >> v;
        add(u,v);   add(v,u); 
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            root = i;
            rootson = 0;
            tarjan(i,0);
        }
    for(int i=1;i<=n;i++)
        if(cut[i])  tot++;
    cout << tot << endl;
    for(int i=1;i<=n;i++)
        if(cut[i])  cout << i << " ";
    return 0;
}