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

我不是女神ヾ 2023-06-01 08:55 2阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define pb push_back
     6 typedef long long ll;
     7 using namespace std;
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 
    24 int N;
    25 int ms[100003];
    26 int G[100003];
    27 int vis[100003];
    28 int tmp[100003];
    29 int passpoint;
    30 int flag = 0;
    31 int dfs(int nw,int len)
    32 {
    33     if(ms[nw])
    34     {
    35         flag = 1;
    36         return ms[nw]+1;
    37     }
    38     if(vis[nw]==-1)
    39     {
    40         passpoint = nw;
    41         ms[nw] = len-tmp[nw];
    42         return len-tmp[nw];
    43     }
    44     tmp[nw] = len;
    45     vis[nw] = -1;
    46     ms[nw] = dfs(G[nw],len+1);
    47     if(flag)
    48         return ms[nw]+1;
    49     tmp[nw] = 0;
    50     if(passpoint==nw)
    51     {
    52         flag = 1;
    53         return ms[nw]+1;
    54     } 
    55     return ms[nw];
    56 }
    57 int main()
    58 {
    59     N = read();
    60     _for(i,1,N+1)
    61         G[i] = read();
    62     _for(i,1,N+1)
    63         if(!ms[i])
    64         {
    65             flag = 0;
    66             passpoint = -1;
    67             dfs(i,0);
    68         }
    69 
    70     _for(i,1,N+1)
    71     printf("%d\n",ms[i]);
    72 
    73     return 0;
    74 }

转载于:https://www.cnblogs.com/Asurudo/p/11507876.html