UVa12442.cpp

#include <bits/stdc++.h>
using namespace std;

#define D(x) (cout << #x << ": " << x << endl)

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << '{';
    for(const T& t : v)
        os << t << ", ";
    return os << '}';
}

vector<bool> vis;

void dfs(int u, vector<vector<int>>& adj, vector<int>& vec)
{
    if(vis[u])
        return;
    vis[u] = true;
    for(int v : adj[u])
        dfs(v, adj, vec);
    vec.push_back(u);
}

int main()
{
    int T;
    scanf("%d", &T);
    for(int cs = 1; cs <= T; ++cs)
    {
        int n;
        scanf("%d", &n);
        vector<vector<int>> adj(n, vector<int>()), adjT(n, vector<int>());

        for(int i = 0; i < n; ++i)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            --u; --v;
            adj[u].push_back(v);
            adjT[v].push_back(u);
        }

        vector<int> cc(n);
        vector<vector<int>> adjC(n, vector<int>());
        vector<int> cst(n, 0);
        vector<int> ma(n);

        vis.assign(n, false);
        vector<int> ts;
        for(int i = 0; i < n; ++i)
            dfs(i, adj, ts);
        vis.assign(n, false);
        reverse(ts.begin(), ts.end());
        for(int i : ts)
            if(!vis[i])
            {
                vector<int> c;
                dfs(i, adjT, c);
                for(int j : c)
                    cc[j] = i;
                cst[i] = c.size();
            }

        for(int i = 0; i < n; ++i)
            for(int j : adj[i])
                if(cc[i] != cc[j])
                    adjC[cc[i]].push_back(cc[j]);
        ts.clear();
        vis.assign(n, false);
        for(int i = 0; i < n; ++i)
            dfs(i, adjC, ts);
        int ans = 0;
        int with = -1;
        for(int i : ts)
        {
            ma[i] = cst[i];
            //printf("cst[%d] = %d\n", i, cst[i]);
            for(int j : adjC[i])
                ma[i] += ma[j];
            if(ma[i] > ans || (ma[i] == ans && i < with))
            {
                ans = ma[i];
                with = i;
            }
        }

        printf("Case %d: %d\n", cs, with+1);
        //printf("ans = %d\n", ans);
    }
    return 0;
}