BOJ 3977 축구 전술

1 개요

BOJ 3977 축구 전술

• 백준 온라인 저지 3977번 문제
• BOJ 44단계

2 C++

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

int N, M;
int dt[100000];
int scc[100000];
int indeg[100000];
int sccCount, componentCount;
vector<vector<int>> adj;
stack<int> stk;

int dfs(int cur) {
    componentCount++;
    dt[cur] = componentCount;
    stk.push(cur);
    int mindt = dt[cur];
    for (int neighbor : adj[cur]) {
        if (!dt[neighbor]) {
            mindt = min(mindt, dfs(neighbor));
        } else if (!scc[neighbor]) {
            mindt = min(mindt, dt[neighbor]);
        }
    }
    if (mindt == dt[cur]) {
        sccCount++;
        while (true) {
            int v = stk.top();
            stk.pop();
            scc[v] = sccCount;
            if (v == cur)
                break;
        }
    }
    return mindt;
}

void solve() {
	sccCount = 0;
	componentCount = 0;
	memset(dt, 0, sizeof(dt));
	memset(scc, 0, sizeof(scc));
	memset(indeg, 0, sizeof(indeg));
	for (int i = 0; i < N; i++) {
		if (!dt[i]) {
			dfs(i);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int neighbor : adj[i]) {
			if (scc[i] == scc[neighbor]) continue;
			indeg[scc[neighbor]]++;
		}
	}
    int res = 0;
    int firstRoot = 0;
	for (int i = 1; i <= sccCount; i++) {
		if (!indeg[i]) {
			firstRoot = i;
			res++;
		}
	}
	if (res > 1) {
		cout << "Confused\n\n";
		return;
	}
	for (int i = 0; i < N; i++) {
		if (scc[i] == firstRoot)
			cout << i << '\n';
	}
	cout << '\n';
}

void sub() {
	cin >> N >> M;
	adj.clear();
	adj.resize(N + 1);
	int u, v;
	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
	}
	solve();
}

int main() {
	int T;
    cin >> T;
    while (T--) {
		sub();
	}
}