【POI每日题解 #9】SKA-Piggy Banks

题目链接

题意:

有一棵环套树

求最少从多少个节点出发能沿边走过整棵树

环套树 并查集求联通块

有几块就砸几个

太简单不发代码了

不过某大佬的环套树找环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

上一篇:DDT模块


下一篇:Oracle Length 和 Lengthb 函数说明 .(用来判断记录值里是否有中文内容)