115A. Party CodeForce題解

原題連結

思路：這題問的是将n個人分成res組，且每個組不存在直接上下級關系。是以我們隻需要求出每棵樹裡面最深的深度就是res。 用并查集來求。我用兩種方法，狀态壓縮和不狀态壓縮都做一遍，由于這題需要求深度，狀态壓縮是延遲更新 需要在求res之前對所有i都額外一次壓縮

//方法一
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
int p[N],d[N];

int find(int x)  // 并查集
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x]+=d[p[x]];
        p[x] = root;
    }
    return p[x];
}
int main()
{
    int n;
    cin>>n;
    
    for (int i = 1; i <= n; i ++ )p[i]=i,d[i]=0;
    
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        if(x==-1)continue;
        int pa=find(i),pb=find(x);
        if(pa!=pb)
        {
            d[i]=d[x]+1;
            p[pa]=pb;
        }
    }
    int res=0;
    for (int i = 1; i <= n; i ++ )find(i);
    for (int i = 1; i <= n; i ++ )
    {
        res=max(res,d[i]);
    }
    cout<<res+1;
    return 0;
}
           

//方二
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
int p[N];

int find(int x)  // 并查集
{
    int deep=1;
    while (p[x] != x)
    {
        x = p[x];
        deep++;
    }
    return deep;
}
int main()
{
    int n;
    cin>>n;
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%d", &x);
        if(x==-1)p[i]=i;
        else p[i]=x;
    }
    int res=0;
    for (int i = 1; i <= n; i ++ )
    {
        res=max(res,find(i));
    }
    cout<<res;
    return 0;
}