Codeforces 116C - Party(dfs)

1604 단어 codeforces
n 사람마다 상사가 한 명씩 있다.상사 관계는 전달성을 가지고 있다.최소한 사람을 몇 조로 나누어야 하며, 각 조의 모든 상사나 간접 상사는 이 조에 없다.문제를 받으면 나무의 직경으로 포를 쏘았다...
정해는 무환삼림으로 향하는 가장 긴 길이다.각 노드 dfs에서 가장 긴 길을 찾으면 됩니다.
 
#include<algorithm>

#include<iostream>

#include<cstring>

#include<fstream>

#include<sstream>

#include<cstdlib>

#include<vector>

#include<string>

#include<cstdio>

#include<bitset>

#include<queue>

#include<stack>

#include<cmath>

#include<map>

#include<set>

#define FF(i, a, b) for(int i=a; i<b; i++)

#define FD(i, a, b) for(int i=a; i>=b; i--)

#define REP(i, n) for(int i=0; i<n; i++)

#define CLR(a, b) memset(a, b, sizeof(a))

#define debug puts("**debug**")

#define LL long long

#define PB push_back

#define MP make_pair

using namespace std;



const int maxn = 2222;

int n, x, fa, len, t, vis[maxn];

vector<int> G[maxn];



void dfs(int u, int fa, int now)

{

    len = max(len, now);

    REP(i, G[u].size())

    {

        int v = G[u][i];

        if(v != fa) dfs(v, u, now+1);

    }

}



int main()

{

    scanf("%d", &n);

    x = -1;

    FF(i, 1, n+1)

    {

        scanf("%d", &fa);

        if(fa != -1)

        {

            x = fa;

            G[fa].PB(i);

        }

        else vis[i] = 1;

    }

    int ans = 1;

    FF(i, 1, n+1) if(vis[i])

    {

        len = 0;

        dfs(i, -1, 0);

        ans = max(ans, len + 1);

    }

    printf("%d
", ans); return 0; }

 

좋은 웹페이지 즐겨찾기