洛谷 P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

题目传送门

解题思路:

这道题不怎么会做,所以就看了题解.......

首先这题n点n边还连通,那显然这题就是一棵n个树上多了一条奇奇怪怪的边(返祖边),既然只有一条返祖的边,那么也就等价于这棵树上有且仅有一个环.所以直接讨论一个点是否在环上,如果在则答案与它指向点相同,不然就等于它指向点答案+1,具体就直接大力dfs,每个点最多访问一次,故总复杂度为O(n).(这里注意下dfs不一定只跑一遍就能访问所有的点,但显然跑一次dfs一定可以处理掉环)

//https://www.luogu.org/blog/user51742/solution-p2921

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int n,to[100001],deep[100001],ans[100001];
 7 bool p[100001];
 8 
 9 void dfs(int k,int dep) {
10     p[k] = 1;
11     deep[k] = dep;
12     if(ans[to[k]]) ans[k] = ans[to[k]] + 1;//如果已求得指向点答案,那么它与指向点不可能同在环上,故答案为指向点+1 
13     else if(deep[to[k]]) {//如果跑到这次dfs已访问过的点,说明找到环了,暴力更新环上所有点答案
14         ans[k] = deep[k] - deep[to[k]] + 1;
15         int now = to[k];
16         while(now != k) {
17             ans[now] = ans[k];
18             now = to[now];
19         }
20     }
21     else {//如果跑完指向点而它本身答案没有更新,那么说明它不在环上,答案为指向点+1 
22         dfs(to[k],dep + 1);
23         if(!ans[k])
24             ans[k] = ans[to[k]] + 1;
25     }
26 }
27 
28 int main()
29 {
30     scanf("%d",&n);
31     for(int i = 1;i <= n; i++)
32         scanf("%d",&to[i]);
33     for(int i = 1;i <= n; i++)
34         if(!p[i])
35             dfs(i,0);
36     for(int i = 1;i <= n; i++)
37         printf("%d
",ans[i]);
38     return 0;
39 }