牛客2020寒假训练营6-B

牛客2020寒假训练营6-B

七月 15, 2020

图

题意
有n个点 每个点只有一个出度 问最长路径长度

基于基环树的结论 从一个入度为0的点开始一定最终通向环

或用tarjan缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# include<bits/stdc++.h>

using namespace std;

# define FI first

# define SE second

# define LL long long

# define LDB long double

# define MP make_pair

# define PII pair<int,int>

# define SZ(a) (int)a.size()

const LDB pai = acos(-1.0L);
const LDB eps = 1e-10;
const LL mod = 1e9+7;
const int MXN = 1e6+5;
int to[MXN];
int du[MXN]; ///入度
int h[MXN];
int dp[MXN];
int dfs(int u){
    if(dp[u]) return dp[u];
    return dp[u]=dfs(to[u])+1;
}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&to[i]);
    for(int i=1;i<=n;i++) du[to[i]]++;
    queue<int>q;
    for(int i=1;i<=n;i++) if(du[i]==0) q.push(i);///入度为0的作为出发点
    while(!q.empty()){///bfs遍历图找到环入口
		      ///岔路必然连接多个出发点最后被排除而环的入口不会被排除 即入度不为0的节点
        int now=q.front();q.pop();
        du[to[now]]--;
        if(du[to[now]]==0) q.push(to[now]);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(du[i]){
            int now=i,s=i;
            vector<int>v;
            v.push_back(s);du[s]--;
            while(to[now]!=s)
                du[to[now]]--,v.push_back(to[now]),now=to[now];
            for(auto j:v) dp[j]=SZ(v);
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dfs(i));
    }
    cout<<ans<<'\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


# include <iostream>

# include <cstdio>

# include <cstring>

# include <algorithm>

# include <cmath>

using namespace std;

const int N = 1000050;

int to[N], siz[N], n, vis[N], ins[N], sta[N];

int dfs(int x){

	if(siz[x]) return siz[x];

	return siz[x] = 1 + dfs(to[x]);

}

///ins是找环用的vis 每次要记得清空ins 否则下次还会找到同一个环
///如果是某条直线多个点通向同一个环那么直线的点会多次访问ins避免重复计算相同的环
///sta[0] 记录路径长度 sta[j]表示该路径第几个点在原图中的下标
int main()
{
	int i, j, k, h;
	scanf("%d", &n);
	for(i = 1; i <= n; i ++)
  		scanf("%d", &to[i]);
	for(i = 1; i <= n; i ++){
  		if(vis[i] == 0){
        	j = i;
       		while(vis[j] == 0){
       			sta[++ sta[0]] = j;
        		vis[j] = ins[j] = 1;
         		j = to[j];
     		}
      		if(ins[j]){
        		k = j, h = 0;
                do{
        			k = to[k];
            		h ++;
            	}while(k != j);
           		do{
               	   	k = to[k];
                    siz[k] = h;
           		}while(k != j);
        	}
        	while(sta[0]){
            	ins[sta[sta[0]]] = 0;
            	sta[0] --;
        	}
    	}
	}
	for(i = 1, h = 0; i <= n; i ++)
    	h = max(h, dfs(i));
		printf("%d", h);
	return 0;
}