Problem

“… so forward this to ten other people, to prove that you believe the emperor has new clothes.”
Aren’t those sorts of emails annoying?
Martians get those sorts of emails too, but they have an innovative way of dealing with them.
Instead of just forwarding them willy-nilly, or not at all, they each pick one other person they know
to email those things to every time – exactly one, no less, no more (and never themselves). Now, the Martian clan chieftain wants to get an email to start going around, but he stubbornly only wants to send one email. Being the chieftain, he managed to find out who forwards emails to whom, and he wants to know: which Martian should he send it to maximize the number of Martians that see it?

Input

The first line of input will contain T (≤ 20) denoting the number of cases.
Each case starts with a line containing an integer N (2 ≤ N ≤ 50000) denoting the number of
Martians in the community. Each of the next N lines contains two integers: u v (1 ≤ u, v ≤ N, u ̸= v)
meaning that Martian u forwards email to Martian v.

Output

For each case, print the case number and an integer m, where m is the Martian that the chieftai
should send the initial email to. If there is more than one correct answer, output the smallest number.

Sample Input

Sample Output

3
3
1 2
2 3
3 1
4
1 2
2 1
4 3
3 2
5
1 2
2 1
5 3
3 4
4 5

Sample Output

Case 1: 1
Case 2: 4
Case 3: 3

문제 풀이

dfs를 이용해서 풀었다.
사이클을 한 덩어리로 포함하여 트리 구성했다.
그리고 최대 cover하는 수를 출력했다

  • 도달할 수 있는 것들은 다 묶음
  • 다른 그룹 방문할때는 하나의 그룹으로 포함x

답안 코드

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX_N   50000 +1

#define UNVISITED   0
#define EXPLORED    1
#define VISITED     2

vector<int> adj[MAX_N];
int cover[MAX_N];       // 몇명에게 forwarding하는지 갯수
int visit[MAX_N];
int dfs_low[MAX_N];
int dfs_num[MAX_N];
int dfs_counter;
int counterToV[MAX_N];

int T;
int N;

void dfs(int u){
    visit[u] = EXPLORED;
    dfs_low[u] = dfs_num[u] = dfs_counter++;
    cover[u] = 1;
    counterToV[dfs_low[u]] = u;
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i];
        if(visit[v] == UNVISITED)
            dfs(v);
        else if(visit[v] == VISITED && dfs_low[v] != dfs_num[u]){
            // found cycle group, not update dfs_low(another group)
            cover[u] += cover[counterToV[dfs_low[v]]];
            continue;
        }
        cover[u] += cover[v];
        dfs_low[u] = min(dfs_low[u], dfs_low[v]);
    }
    visit[u] = VISITED;
}

int main(){
    scanf("%d\n", &T);
    for(int t = 1; t <= T; ++t){
        scanf("%d\n", &N);
        int a,b;
        for(int i = 0; i < N; ++i){
            scanf("%d %d\n", &a, &b);
            adj[a].push_back(b);
        }
        
        dfs_counter = 1;
        for(int i = 1; i <= N; ++i)
            if(visit[i] == UNVISITED)
                dfs(i);
        
        int max_cover = 0;
        int ans = 0;
        for(int i = 1; i <= N; ++i)
            if(max_cover < cover[i]){
                max_cover = cover[i];
                ans = i;
            }
        
        printf("Case %d: %d\n", t, ans);
        
        memset(visit, UNVISITED, sizeof(visit));
        for(int i = 1; i <= N; ++i)
            adj[i].clear();
    }
    return 0;
}

문제 위치 – https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3873