3977번: 축구 전술 – SCC

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

1. SCC를 사용하여 그래프를 방향성 비순환 그래프(DAG)로 변환합니다.

2. in-order가 0인 정점을 찾는다. 그런 정점이 있으면 SCC를 반환하고, 2개 이상이면 Confused를 반환한다.

동일한 SCC로 묶인 정점의 DFS_min 값은 다를 수 있습니다. 왜냐하면 인접한 두 꼭지점의 DFS_min 값이 다르고 각도를 추가하여 진행하면 항상 잘못된 것입니다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, M;
vector<int> graph(100000); //구역 간 그래프
bool area_exist(100000); //각 구역이 존재하는지 확인

vector<vector<int>> SCC;
int DFS_cnt = 1;
int DFS_num(100000);
int DFS_min(100000);
bool cache(100000);
stack<int> st;

int idx{ 0 };
int SCCID(100000); //SCC vector에서 정점 i가 속한 index
int indegree(100000); //indegree(i) : SCC(i)의 진입차수

void init()
{
    for (int i{ 0 }; i < N; i++) graph(i).clear();
    memset(area_exist, false, sizeof(area_exist));
    SCC.clear();
    DFS_cnt = 1;
    memset(DFS_num, 0, sizeof(DFS_num));
    memset(DFS_min, 0, sizeof(DFS_min));
    memset(cache, false, sizeof(cache));
    memset(SCCID, 0, sizeof(SCCID));
    memset(indegree, 0, sizeof(indegree));
    while (!st.empty()) st.pop();

    idx = 0;
}

void DFS(int u)
{
    DFS_num(u) = DFS_min(u) = DFS_cnt++;
    cache(u) = true;
    st.push(u);

    for (int v : graph(u))
    {
        if (!DFS_num(v)) DFS(v);
        if (cache(v)) DFS_min(u) = min(DFS_min(u), DFS_min(v));
    }

    if (DFS_num(u) == DFS_min(u))
    {
        vector<int> scc;
        while (true)
        {
            int tu{ st.top() }; st.pop();
            scc.push_back(tu);
            cache(tu) = false;
            SCCID(tu) = idx;
            if (tu == u) break;
        }
        sort(scc.begin(), scc.end());
        SCC.push_back(scc);
        idx++;
    }
}

void solve()
{
    cin >> N >> M;

    init(); //초기화

    for (int i{ 1 }; i <= M; i++)
    {
        int A, B; cin >> A >> B;
        graph(A).push_back(B);

        area_exist(A) = true;
        area_exist(B) = true;
    } //입력

    for (int i{ 0 }; i < N; i++)
    {
        if (!area_exist(i))
        {
            cout << "Confused\n\n";
            return;
        }
        if (!DFS_num(i)) DFS(i);
    } //DFS를 이용해 SCC 만들기

    for (auto scc : SCC)
    {
        for (int u : scc)
        {
            for (int v : graph(u))
            {
                if (SCCID(v) != SCCID(u))
                    indegree(SCCID(v))++;
            }
        }
    } //SCC의 진입차수 구하기

    int start{ -1 };
    for (int i{ 0 }; i < idx; i++)
    {
        if (!indegree(i))
        {
            if (start != -1)
            {
                cout << "Confused\n\n";
                return;
            }
            start = i;
        }
    }

    for (int u : SCC(start)) cout << u << "\n";
    cout << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T; cin >> T;
    for (int i{ 1 }; i <= T; i++) solve();
}