Gym - 100502 G - Outing

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>    
#include<cmath>    
#include<queue>    
#include<cstdio>    
#include<queue>    
#include<algorithm>    
#include<cstring>    
#include<string>    
#include<utility>  
#include<map>  
#include<vector>  
#define maxn 200005   
#define E 1005  
#define V 1005  
#define inf 0x3f3f3f3f    
using namespace std;  
typedef long long LL;  
const double eps = 1e-8;  
struct edge  
{  
    int to, next;  
}Edge[E];  
int head[V], e, n;  
int indeg[V]; //联通块的入度和出度数  
int belong[V], low[V], dfn[V], scc, cnt, num[V], connect[V][V];//dfn[]:遍历到u点的时间; low[]:u点可到达的各点中最小的dfn[v];belong[]:该点所属的联通块;scc:联通块个数;  
int S[V], top;//S[]//数组栈  
bool vis[V];//v是否在栈中  
int dp[V][V], k;  
vector<int>p[V];  
int addedge(int u, int v)  
{  
    Edge[e].to = v;  
    Edge[e].next = head[u];  
    head[u] = e++;  
    return 0;  
}  
void tarjan(int u)  
{  
    int v;  
    dfn[u] = low[u] = ++cnt;//开始时dfn[u] == low[u]  
    S[top++] = u;//不管三七二十一进栈  
    vis[u] = true;  
    for (int i = head[u]; i != -1; i = Edge[i].next)  
    {  
        v = Edge[i].to;  
        if (dfn[v] == 0)//如果v点还未遍历  
        {  
            tarjan(v);//向下遍历  
            low[u] = low[u] < low[v] ? low[u] : low[v];//确保low[u]最小  
        }  
        else if (vis[v] && low[u] > dfn[v])//v在栈中，修改low[u]  
            low[u] = dfn[v];  
    }  
    if (dfn[u] == low[u])//u为该强连通分量中遍历所成树的根  
    {  
        ++scc;  
        do  
        {  
            v = S[--top];//栈中所有到u的点都属于该强连通分量，退栈  
            vis[v] = false;  
            belong[v] = scc;  
            num[scc]++;  
        } while (u != v);  
    }  
  
}  
  
int solve()  
{  
    for (int u = 1; u <= n; ++u)  
        if (!dfn[u])  
            tarjan(u);  
    return scc;  
}  
void dfs(int now){  
    dp[now][0] = dp[now][num[now]] = 1;  
    for (int i = 0; i < p[now].size(); i++){  
        dfs(p[now][i]);  
        for (int j = k; j > num[now]; j--){  
            if (dp[now][j])  
                continue;  
            for (int l = 0; l <= j - num[now]; l++){  
                if (dp[now][j - l] && dp[p[now][i]][l]){  
                    dp[now][j] = 1;  
                }  
            }  
        }  
    }  
}  
int main(){  
    memset(head, -1, sizeof(head));  
    scanf("%d%d", &n, &k);  
    for (int i = 1; i <= n; i++){  
        int u;  
        scanf("%d", &u);  
        addedge(u, i);  
    }  
    solve();  
    for (int i = 1; i <= n; i++){  
        for (int j = head[i]; ~j; j = Edge[j].next){  
            if (belong[i] == belong[Edge[j].to]||connect[belong[i]][belong[Edge[j].to]])  
                continue;  
            connect[belong[i]][belong[Edge[j].to]] = 1;  
            p[belong[i]].push_back(belong[Edge[j].to]);  
            indeg[belong[Edge[j].to]]++;  
        }  
    }  
    for (int i = 1; i <= scc; i++){  
        if (!indeg[i])  
            p[0].push_back(i);  
    }  
    dfs(0);  
    for (int i = k; i >= 0; i--){  
        if (dp[0][i]){  
            printf("%dn", i);  
            break;  
        }  
    }  
}