12.9日+基环树 dfs找环

     基环树就是在一棵树上加一条边的图。一般结合其他树形dp、树的直径等题型考察，有一定难度。

处理方法一般都是先找环。

例如这道题目，BZOJ 1791 [Ioi2008] Island 岛屿：https://www.lydsy.com/JudgeOnline/problem.php?id=1791，求基环树森林的树直径之和。后面的树形dp不会，但找环和求以某点为根的子树的深度还是可以的，用dfs。

先粘上求环中点的dfs代码（以前都是并查集，，，）：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include<algorithm>
#include <set>
#include <queue>
#include <stack>
#include<vector>
#include<map>
#include<ctime>
#define ll long long
using namespace std;
const int N=100010,M=1000010;
int head[N];
int ver[M];
int edge[M];
int Next[M];
bool v[N];
int tot;
priority_queue< pair<int,int> >Q;
void add(int x,int y,int z)
{
ver[++tot]=y;
edge[tot]=z;
Next[tot]=head[x];
head[x]=tot;
}
bool flag[N];
int path[N];
int sum;
int dfs(int x,int pre)
{
flag[x]=1;
for(int i=head[x];i;i=Next[i])
{
int vv=ver[i];
//cout<<vv<<endl;
if(!flag[vv])
{
int index= dfs(vv,x);
if(!index)continue;
if(index!=-1)path[++sum]=vv;
if(index==vv)return -1;
else
return index;
}
else if(vv!=pre)
{
//cout<<vv<<" "<<pre<<endl;
path[++sum]=vv;
return vv;
}
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;++i)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
dfs(1,-1);
for(int i=1;i<=sum;++i)cout<<path[i]<<" ";
cout<<endl;
}

更新简洁代码：

#include<bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int N=2e5+100;
using namespace std;
int head[N];
int Next[N];
int ver[N];
int tot;
int deg[N];
int pre[N];
void add(int x,int y)
{
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
int ans[N];
int kk;
int dfn[N];
int cnt=0;
void dfs(int x)
{
dfn[x]=++cnt;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(y==pre[x])continue;
if(dfn[y])
{
if(dfn[y]<dfn[x])continue;
ans[++kk]=y;
for(;y!=x;y=pre[y])ans[++kk]=pre[y];
}
else pre[y]=x,dfs(y);
}
}
int main()
{
int n,m;
while(cin>>n)
{
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1);
sort(ans+1,ans+1+kk);
for(int i=1;i<=kk;++i)cout<<ans[i]<<" ";
}
return 0;
}

The end；

最后

以上就是优秀小笼包为你收集整理的12.9日+基环树 dfs找环的全部内容，希望文章能够帮你解决12.9日+基环树 dfs找环所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。