[3977번] 축구 전술

문제 출처 :

https://www.acmicpc.net/problem/3977

알고리즘 분석 :

문제 해결에 필요한 사항

1. SCC :: http://www.crocus.co.kr/950

이 문제는 SCC를 이용하여 풀 수 있다.

축구 전술을 하는데 진입차수 Indegree가 0인것이 딱 하나 있어야 그 정점을 시작으로하면 모든 그래프를 순회 가능하기 때문이다.

2번 테스트케이스를 보면 

4 4
0 3
1 0
2 0
2 3

진입차수가 0인것이 1,2 두개가 있기에 어느점에서 시작해도 모든 그래프를 순회 할 수 없다. 따라서 Confused이다.

1번 예제의 경우 

4 4
0 1
1 2
2 0
2 3

진입차수가 0인것이 0-1-2로 구성된 SCC이기에 0,1,2 3개가 답이 될 수 있는 것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <memory.h>
 
using namespace std;
 
const int MAX = 101000;
 
vector<vector<int>> adj;
stack<int> s;
 
bool finish[MAX]; // SCC 분리가 완료된 정점 = true
int dfsn[MAX]; // 각 노드 dfs 번호
int SCCnum[MAX]; // SCC의 인덱스 번호
int indegree[MAX];
int cnt; // dfs 번호
int SCCtotal; // SCC 총 개수
 
int dfs(int cur)
{
    dfsn[cur] = ++cnt;
 
    s.push(cur);
 
    int result = dfsn[cur];
 
    int len = adj[cur].size();
 
    for (int i = 0; i < len; i++)
    {
        int next = adj[cur][i];
 
        if (!dfsn[next])
            result = min(result, dfs(next));
 
        else if (!finish[next])
            result = min(result, dfsn[next]);
    }
 
    if (result == dfsn[cur])
    {
        while (1)
        {
            int t = s.top();
            s.pop();
            finish[t] = true;
            SCCnum[t] = SCCtotal;
 
            if (t == cur)
                break;
        }
 
        SCCtotal++;
    }
 
    return result;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
    while (tc--)
    {
        int V, E;
        scanf("%d %d", &V, &E);
 
        memset(finish, false, sizeof(finish));
        memset(dfsn, 0, sizeof(dfsn));
        memset(SCCnum, 0, sizeof(SCCnum));
        memset(indegree, 0, sizeof(indegree));
        adj.clear();
        adj.resize(V + 1);
        cnt = 0;
        SCCtotal = 0;
 
        for (int i = 0; i < E; i++)
        {
            int from, to;
            scanf("%d %d", &from, &to);
            adj[from].push_back(to);
        }
 
        for (int i = 0; i < V; i++)
            if (!dfsn[i])
                dfs(i);
 
        // 진입 차수를 구한다.
        for (int i = 0; i < V; i++)
            for (int j : adj[i])
                if (SCCnum[i] != SCCnum[j])
                    indegree[SCCnum[j]]++;
 
        // 진입 차수가 0인 부분 즉, 시작 부분이 있다면 target과 cntdegree를 계산 
        int cntdegree = 0;
        int target = 0;
        for (int i = 0; i < SCCtotal; i++)
            if (indegree[i] == 0)
                target = i, cntdegree++;
 
        // 진입 차수가 2개 이상이면 Confused
        if (cntdegree > 1)
            printf("Confused\n");
 
        // 진입차수가 1일 때 그 SCC 넘버랑 같은 정점을 모두 출력
        else
            for (int i = 0; i < V; i++)
                if (SCCnum[i] == target)
                    printf("%d\n", i);
 
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>