#42976: Answer(C++)


e970901@gmail.com (張子祥)

學校 : 不指定學校
編號 : 258634
來源 : [61.61.72.78]
最後登入時間 :
2024-11-18 20:35:56
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [61.61.72.78] | 發表日期 : 2024-10-13 14:21

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int a=0;
    int up = 0;
    int down = 0;
};
int head = 0;
long long ans;
vector<int> v;
int main()
{
    //Processing Data
    int n;
    cin >> n;
    Node Nodes[n+1];
    for(int i=1;i<n+1;i++)
    {
        int a;
        cin >> a;
        for(int j=0;j<a;j++)
        {
            int b;
            cin >> b;
            Nodes[i].down = 1;
            Nodes[b].up = i;
        }
    }

    //Finding head and bottom node
    for(int i=1;i<n+1;i++)
    {
        if(Nodes[i].up==0)
        {
            head = i;
        }
        if(Nodes[i].down==0)
        {
            v.push_back(i);
        }
    }

    //Bottom to Top
    for(int i=0;i<v.size();i++)
    {
//        cout << "Starting from " << v[i] <<endl;
        long long c=v[i];
        long long  j=0;
         while(true)
        {
            j = Nodes[c].up;
//            cout << "Tranversed to " << j << endl;
            Nodes[j].a = max(Nodes[c].a+1,Nodes[j].a); //Compare
            c=j;
            if(j==head)
            {
                break;
            }
        }
    }
    for(auto i: Nodes)
    {
        ans+=i.a;
    }
    cout << head<< endl;
    cout << ans;
}

 

 

 

 

 

 
ZeroJudge Forum