基环树
基环树定义:一个有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链来维护环的信息