首页 > 其他 > 详细

【模板】割点(割顶)

时间:2019-07-08 23:54:02      阅读:173      评论:0      收藏:0      [点我收藏+]

题目背景

割点

题目描述

给出一个n个点,m条边的无向图,求图的割点。

输入格式

第一行输入n,m

下面mm行每行输入x,y表示xy有一条边

输出格式

第一行输出割点个数

第二行按照节点编号从小到大输出节点,用空格隔开

输入输出样例

输入 #1
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
输出 #1
1 
5

说明/提示

对于全部数据,n20000,m100000

点的编号均大于0小于等于n

tarjan图不一定联通。

 

有一条边(u, v),如果v未访问过,继续DFS,DFS完之后,low[u]=min(low[u], low[v]);

如果v访问过(且u不是v的父亲),就不需要继续DFS了,一定有dfn[v]<dfn[u],low[u]=min(low[u], dfn[v])。

 

#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;

stack<int>q;

int n,m,cnt,sum,idx;

int dfn[20005],low[20005],in[20005],head[20005],ch[20005];

struct node{ 
    int from,to,next;
}edge[200005];

void add(int from,int to) { 
    edge[++cnt].from=from;
    edge[cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
} 

void tarjan(int now,int fa){ 
    int son=0;
    dfn[now]=low[now]=++idx;
    in[now]=1;
    q.push(now);
    for(int i=head[now];i;i=edge[i].next){ 
        int to=edge[i].to;
        if(!dfn[to]){ 
            son++;
            tarjan(to,now);
            low[now]=min(low[now],low[to]);
            if(low[to]>dfn[now]&&!ch[now]){
                ch[now]=1;
                sum++;
            }
        } 
        else if(to!=fa&&dfn[to]<dfn[now]){
            low[now]=min(low[now],dfn[to]);
        }
    } 
    if(now==fa&&son>=2){
        ch[now]=1;
        sum++;
    }
} 
int main() { 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) { 
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    } 
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i,i);
        }
    }
    printf("%d\n",sum);
    for(int i=1;i<=n;i++){
        if(ch[i]){
            printf("%d ",i);
        }
    }
    return 0;
}

 

【模板】割点(割顶)

原文:https://www.cnblogs.com/hrj1/p/11154808.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!