(UVA) 12442 - Forwarding Emails

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3873

DFS就對了，不要想這麼多XD！

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 50002;
bool visit[MAX_N];
int rudu[MAX_N];
int ans[MAX_N];
int root[MAX_N];
vector<int> edg[MAX_N];

void init(int n) {
    memset(rudu,0,sizeof(rudu));
    for (int x=0;n>=x;x++) {
        edg[x].clear();
        visit[x]=false;
        ans[x]=0;
        root[x]=x;
    }
}

int DFS(int id) {
    visit[id]=true;
    int total=0;
    for (auto i = edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) {
            total = max(total,DFS(tmp)+1);
        }
    }
    visit[id]=false;
    return ans[id]=total;
}

int main () {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int T;
    scanf("%d",&T);
    for (int qq=0;T>qq;qq++) {
        int n;
        scanf("%d",&n);
        init(n);
        for (int x=0;n>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            rudu[j]++;
            edg[i].push_back(j);
        }
        //don't be so complicated, just DFS !!!
        int mn=-1;
        int id=-1;
        for (int x=1;n>=x;x++) {
            if (ans[x]==0) DFS(x);
            if (ans[x]>mn) {
                mn=ans[x];
                id=x;
            }
        }
        printf("Case %d: ",qq+1);
        printf("%d\n",id);
    }
}