백준[3977] 축구 전술

문제 설명

문제 링크

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

풀이

이 문제는 코사라주 알고리즘을 이용하여 SCC를 구해서 풀 수 있다.

백준 4196 도미노 와 매우 비슷하다.

도미노 문제와 동일하게 dfs를 돌리며 방문할 노드가 없을 때 스택에 추가하면 stack의 top에는 가장 많은 곳을 갈 수 있는 노드가 위치하게 된다. 그렇기 때문에 stack의 top에 있는 노드를 시작으로 다시 dfs를 돌려 모든 노드를 방문할 수 있는지 판별하고, 만약 모두 방문할 수 있다면 top에 있는 노드의 SCC를 출력하고 그렇지 않다면 Confused를 출력한다.

코드

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

using namespace std;

vector<vector<int>> v;
vector<vector<int>> rev;
stack<int> s;
vector<int> ans;
bool visited[100005];

void dfs(int cur) {
    visited[cur] = true;
    for (auto nxt : v[cur]) {
        if (!visited[nxt]) dfs(nxt);
    }
    s.push(cur);
}

void rev_dfs(int cur) {
    visited[cur] = true;
    ans.push_back(cur);
    for (auto nxt : rev[cur]) {
        if (!visited[nxt]) rev_dfs(nxt);
    }
}

void check_dfs(int cur) {
    visited[cur] = true;
    for (auto nxt : v[cur]) {
        if (!visited[nxt]) check_dfs(nxt);
    }
}

void solve() {
    int n, m; scanf("%d %d", &n, &m);
    v.clear(); v.resize(n + 1);
    rev.clear(); rev.resize(n + 1);
    ans.clear();
    while (m--) {
        int a, b; scanf("%d %d", &a, &b);
        v[a].push_back(b);
        rev[b].push_back(a);
    }
    memset(visited, 0, sizeof visited);
    for (int i = 0; i < n; i++)  {
        if (!visited[i]) dfs(i);
    }
    
    memset(visited, 0, sizeof visited);
    check_dfs(s.top());
	
    //top에 있는 노드를 시작으로 dfs를 돌릴 때 모든 노드를 방문할 수 있는지 확인
    bool flag = true;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) flag = false;
    }

    if (flag) {
    	//scc를 구함
        memset(visited, 0, sizeof visited);
        rev_dfs(s.top());
        sort(ans.begin(), ans.end());
        for (auto k : ans) printf("%d\n", k);
        printf("\n");
    } else {
        printf("Confused\n\n");
    }
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        solve();
        getchar();
    }
}