tarjan算法求割点

2020-12-27 10:28

阅读：715

标签：continue bsp ace str 存在 clear names while second

点双连通分量：在一个无向图中，存在一个极大子图，删除任意一个节点之后该图仍然是一个连通图。

割点：在一个无向图中，存在一个节点，删除这个节点之后，该无向图会被分为若干个连通图（个数大于一），则该点为割点。

#include 
#include 
#include 
#include 
#include 
#include using namespace std;

#define ll long long
#define pb push_back
#define fi first
#define se second

const int N = 2e4 + 10;
int dfn[N]; //时间戳
int low[N]; //能到达最早点
int cut[N]; //是否是割点
vectorint > E[N]; //边
int tim;//dfs序号
int root; //每个连通图的出发点
int cut_cnt; //割点数量
int n, m; //点数  边数


//时间复杂度  O(m)
//割点条件
//(1)该点为最初点root，且该点之下至少存在左图和右图
//(2)该点不u为root，但是该点之后的点无法到达u之前的点

void init(int n){
    for(int i = 1; i i){
        dfn[i] = low[i] = 0;
        cut[i] = 0;
        E[i].clear();
    }
    tim = cut_cnt = 0;
}

void tarjan(int now, int pre){
    dfn[now] = low[now] = ++tim;

    int son = 0;//图个数
    for(auto to : E[now]){
        
        if(to == pre) continue;

        if(!dfn[to]){
            ++son;
            tarjan(to, now);
            low[now] = min(low[now], low[to]);
            //(2)该点不u为root，但是该点之后的点无法到达u之前的点
            if(now != root && dfn[now] 1;
        }else low[now] = min(low[now], dfn[to]);
    }

    //(1)该点为最初点root，且该点之下至少存在左图和右图
    if(now == root && son > 1) cut[now] = 1;
}

void show_info(){

    //割点数量
    printf("\ncut point ‘s number = %d\n", cut_cnt);
    //割点信息
    printf("they‘ re : ");
    for(int i = 1; i i){
        if(cut[i]) printf("(%d) ", i);
    }
    printf("\n\n");
}


void solve(){

    while(~scanf("%d%d", &n, &m)){
        //scanf("%d%d", &n, &m);
        //初始化每组数据
        init(n);
        
        //读边
        for(int i = 1; i i){
            int u, v;
            scanf("%d%d", &u, &v);
            E[u].pb(v);
            E[v].pb(u);
        }

        //可能不是一个连通图
        for(int now = 1; now now){
            if(!dfn[now]){
                root = now;
                //这样可以防止自环的情况
                tarjan(now, now);
            }
        }
        //统计割点个数
        for(int i = 1; i i){
            if(cut[i]) ++cut_cnt;
        }
        show_info();
    }
}

int main(){
    
    solve();    
    //cout 
    return 0;
}

tarjan算法求割点

标签：continue bsp ace str 存在 clear names while second

原文地址：https://www.cnblogs.com/SSummerZzz/p/13032794.html

上一篇：python实现文件读取以及字段统计

下一篇：Python测试基于websocket协议的即时通讯接口【多测师】

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：tarjan算法求割点
文章链接：http://soscw.com/essay/38568.html

亲，登录后才可以留言！

tarjan算法求割点

评论

热门文章

推荐文章

最新文章

置顶文章

tarjan算法 求割点

评论

热门文章

推荐文章

最新文章

置顶文章

tarjan算法求割点