Tuesday, 23 August 2016

UVa 10926 - How Many Dependencies?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool c[109];
vector<ll>graph[109];
ll ans[109];
ll cnt;
void dfs(ll n)
{
    c[n]=1;
    for(ll i=0;i<graph[n].size();i++)
    {
        ll tmp=graph[n][i];
        if(c[tmp]==0)
        {
            cnt++;
            dfs(tmp);
        }
    }
}
int main()
{
    ll i,j,k,l,m,n,test;
    while(1)
    {
        cin>>n;
        if(n==0)
            break;
        for(i=0;i<109;i++)
        {
            graph[i].clear();
        }
        for(i=1;i<=n;i++)
        {
            cin>>m;
            for(j=1;j<=m;j++)
            {
                cin>>k;
                graph[i].push_back(k);
            }
        }
        //cout<<1111<<endl;
        for(i=1,k=1;i<=n;i++)
        {
            memset(c,0,sizeof(c));
            cnt=0;
            dfs(i);
            ans[k]=cnt;
            //cout<<ans[k]<<endl;
            k++;
        }
        ll mx=-111;
        ll res;
        for(i=1;i<k;i++)
        {
            if(ans[i]>mx)
            {
                mx=ans[i];
                res=i;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

No comments:

Post a Comment