Java教程

初学基环树

本文主要是介绍初学基环树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

基环树

基环树定义:一个有n个点,n条边的连通图;

ad:任意的子图的边不会超过点数

基环内向树(森林):所有的点都有且仅有一条出边

基环外向树(森林):所有的点都有且仅有一条入边

理解方式:

1.将基环树看作一棵树上,多了一条边,

2.(解题通法)我们取出环边,然后环上每个节点都会引出一个以此为根的一个子树

判环

bool dfs(int u,int pre){
    if(vis[u]){vis[u] = 2;return 1;}
    for(int i=lst[u];i;i=nex[i]){
        if(i==(pre^1))continue;
        int v = en[i];
        if(dfs(v)){
            if(vis[u]==2)return 0;
            vis[u] = 1;return 1;
        }
	}
    return 0;
}

快捷方式

如果我们给出的节点都是一一对应的一个to[i]节点,那么我们可以用并查集和跳to链来维护环的信息

例题(待补全国庆作业表

这篇关于初学基环树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航