Forwarding Mail V.02(SCC+DAG)

#include <bits/stdc++.h>
using namespace std;
#define MAX 50005
int vertex, edges;

int indegree[MAX];
int deliver[MAX];
int low[MAX];
int disc[MAX];

bool taken[MAX];
int Color[MAX];

vector<int> Graph[MAX];
vector<int> n_Graph[MAX];
vector<int> scc_List;
stack<int> st;
map<int, int> Map;

int Time = 0, color = 0;

void color_SCC(int boss) {
    int Size = (int) scc_List.size();
    for (int i = 0; i < Size; i++) {
        boss = min(boss, scc_List[i]);
    }
    deliver[color] = Size - 1;
    for (int i = 0; i < Size; i++) {
        Color[scc_List[i]] = color;
    }
    Map[color] = boss;
    color++;
}

void build_DAG() {
    for (int u = 0; u < vertex; u++) {
        for (int j = 0; j < (int) Graph[u].size(); j++) {
            int v = Graph[u][j];
            if (Color[u] != Color[v]) {
                n_Graph[Color[u]].push_back(Color[v]);
            }
        }
    }
}

void run_Tarjan_SCC(int u) {
    disc[u] = low[u] = ++Time;
    taken[u] = true;
    st.push(u);

    int Size = Graph[u].size();
    for (int i = 0; i < Size; i++) {
        int v = Graph[u][i];
        if (disc[v] == -1) {
            run_Tarjan_SCC(v);
            low[u] = min(low[u], low[v]);
        } else if (taken[v] == true) {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (disc[u] == low[u]) {
        scc_List.clear();
        scc_List.push_back(u);
        while (st.top() != u) {
            int adj = st.top();
            taken[adj] = false;
            st.pop();
            scc_List.push_back(adj);
        }
        int adj = st.top();
        taken[adj] = false;
        st.pop();
        color_SCC(u);
    }
}

void find_SCC() {
    memset(low, -1, sizeof(low));
    memset(disc, -1, sizeof(disc));
    memset(taken, false, sizeof(taken));
    Time = -1;
    for (int i = 0; i < vertex; i++) {
        if (disc[i] == -1) {
            run_Tarjan_SCC(i);
        }
    }
    build_DAG();
}

int visited[MAX];
int max_people = 0, result = 1;

int DFS(int u) {
    int cnt = 0;
    for (int i = 0; i < (int) n_Graph[u].size(); i++) {
        int v = n_Graph[u][i];
        if (visited[v] == 0) {
            visited[v] = 1;
            cnt = DFS(v) + 1;
        }
    }
    return cnt;
}

int topological_sort() {
    find_SCC();
    for (int u = 0; u < color; u++) {
        for (int j = 0; j < (int) n_Graph[u].size(); j++) {
            int v = n_Graph[u][j];
            indegree[v]++;
        }
    }
    for (int u = 0; u < color; u++) {
        if (indegree[u] == 0) {
            memset(visited, 0, sizeof(visited));
            visited[u] = 1;
            int ret = DFS(u) + 1 + deliver[u];
            if (ret > max_people) {
                max_people = ret;
                result = u;
            }
        }
    }
    return Map[result] + 1;
}

void initialize() {
    Map.clear();
    color = 0;
    max_people = 0;
    result = 1;
    memset(indegree, 0, sizeof(indegree));
    memset(deliver, 0, sizeof(deliver));
    for (int i = 0; i < vertex; i++) {
        Graph[i].clear();
        n_Graph[i].clear();
    }
}

void print_Graph() {
    for (int i = 0; i < color; i++) {
        printf("Neighbors of %d :", i);
        int Size = (int) n_Graph[i].size();
        for (int j = 0; j < Size; j++) {
            printf(" -> %d", n_Graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int nCase, u, v;
    scanf("%d", &nCase);
    for (int cs = 1; cs <= nCase; cs++) {
        scanf("%d", &vertex);
        initialize();
        for (int i = 0; i < vertex; i++) {
            scanf("%d %d", &u, &v);
            u--;
            v--;
            Graph[u].push_back(v);
        }
        int res = topological_sort();
        printf("Case %d: %d\n", cs, res);
    }
}