题意:
有一棵环套树
求最少从多少个节点出发能沿边走过整棵树
环套树 并查集求联通块
有几块就砸几个
太简单不发代码了
不过某大佬的环套树找环dfs让我研究了好久…
贴一下以Orz
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=;
int vis[MAXN],pa[MAXN];
int n,ans;
inline void dfs(int x,int type)
{
if(type==)
{
if(vis[x]==)
{
++ans;//新环
return;
}
else if(vis[x]==)return;//在一个以前走过的块里 不统计
}
else
{
if(vis[x]==)return;
}
vis[x]=type;
dfs(pa[x],type);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
{
scanf("%d",&pa[i]);
}
for(int i=;i<=n;++i)
{
if(!vis[i])
{
dfs(i,);//检测是否为新环
dfs(i,);//标记已统计的环
}
}
printf("%d",ans);
return ;
}
Orz