题解 P2921 【[USACO08DEC]在农场万圣节Trick or Treat on the Farm】
sigland
2018-05-08 19:14:09
发篇蒟蒻至极的题解...(不懂缩点,tarjan.jpg)
首先这题n点n边还tmd连通,那显然这题就是一棵n个树上多了一条奇奇怪怪的边(返祖边),既然只有一条返祖的边,那么也就等价于这棵树上有且仅有一个环.所以直接讨论一个点是否在环上,如果在则答案与它指向点相同,不然就等于它指向点答案+1,具体就直接大力dfs,每个点最多访问一次,故总复杂度为O(n).(这里注意下dfs不一定只跑一遍就能访问所有的点,但显然跑一次dfs一定可以处理掉环)
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,to[100010],dp[100010],deep[100010];
bool vis[100010];//是否访问
void dfs(int pos,int dep)
{
vis[pos]=1;deep[pos]=dep;
if(dp[to[pos]])dp[pos]=dp[to[pos]]+1;//如果已求得指向点答案,那么它与指向点不可能同在环上,故答案为指向点+1
else if(deep[to[pos]])//如果跑到这次dfs已访问过的点,说明找到环了,暴力更新环上所有点答案
{
dp[pos]=(deep[pos]-deep[to[pos]]+1);
int nw=to[pos];
while(nw!=pos)
{
dp[nw]=dp[pos];
nw=to[nw];
}
}
else //如果跑完指向点而它本身答案没有更新,那么说明它不在环上,答案为指向点+1
{
dfs(to[pos],dep+1);
if(!dp[pos])dp[pos]=dp[to[pos]]+1;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&to[i]);
for(int i=1;i<=n;i++)
if(!vis[i])dfs(i,0);//没访问过就dfs
for(int i=1;i<=n;i++)
printf("%d\n",dp[i]); //输出
}
```