10926 - How Many Dependencies?

jd3

在演算法筆記裡有出現這個例題
http://www.csie.ntnu.edu.tw/~u91029/Reachability.html
但我覺得看了好像更不清楚XD

翻譯：http://luckycat.kshs.kh.edu.tw/homework/q10926.htm

題義釐清：只要有任何直接或間接關係都算
                  記得是輸出最多依賴關係的「編號」

解題方法： DFS 或 BFS 看經過多少點
                   時間限制很寬鬆                   隨便搜一下幾乎不用考慮效率


CODE：(這篇有點亂)
/*
    UVA 10926
    AC
    22 ms
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;



int n;
vector<int> list[128];
int dist[128];
bool vist[128];


int dfs(int node)
{
    vist[node] = true;   
    int d = 0;
    for(int i = 0 ; i < list[node].size() ; i++)
        if(!vist[list[node][i]])
            d += dfs(list[node][i]);
   
    return dist[node] = d+1;
}


int main()
{
    int t;
    int depend;
   
    while(1)
    {
        scanf("%d",&n);
        if(n==0)
            return 0;
            
        //init
        for(int i = 0 ; i <= n ; i++)
            list[i].clear();
        
        
        //input
        for(int i = 1 ; i <= n ; i++)
        {
            scanf("%d",&t);
            for(int j = 1 ; j <= t ; j++)
            {
                scanf("%d", &depend);
                list[i].push_back(depend);
            }
        }
        
        
        int most = -1;
        int ans;
        for(int i = 1 ; i <= n ; i++)
        {
            memset(dist,-1,sizeof(dist));
            memset(vist,0,sizeof(vist));
            int a = dfs(i);
            if(a > most)
            {
                most = a;
                ans = i;
            }
        }
        printf("%d\n",ans);
    }
   
   
    return 0;
}