[백준 26146] 즉흥 여행

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

 

문제의 조건에

• 우선 여행을 시작할 나라를 정한 뒤, 그 나라로 간다.
• 그 뒤로, 현재 있는 나라에서 출발하는 항공편 중 원하는 걸 골라서 탄다.
• 철민이는 하나의 나라를 여러 번 방문할 수 있으며, 하나의 항공편을 여러 번 사용할 수 있다

를 보면 무작위 정점에서 출발해서 모든 정점을 방문할 수 있는지 없는지 확인하는 문제이다

 

예제 1번과 2번의 그림을 보면 아주 좋은 힌트가 되는데

1번의 그림을 SCC로 구성해보면 {1, 2, 3, 4}가 되고, 2번 그림에서 SCC를 구성해보면 {1}, {2, 3, 4}로 구성된다

 

SCC의 갯수가 1개면 무작위 정점에서 어딜 가든 모든 정점이 도착 가능한 경우고 SCC의 경우가 2개 이상이면 아닌 경우이다

 

#include <bits/stdc++.h>
// V = 200000, E = 500000;
using namespace std;
int N, M, id = 1, scc[200001];
bool finished[200001];
vector<int> arr[200001];
vector<vector<int>> res;
stack<int> s;
int dfs(int current);
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M;
    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        arr[u].push_back(v);
    }
    for(int i = 1; i <= N; i++) {
        if(scc[i] == 0) {
            dfs(i);
        }
    }
    cout << (res.size() == 1 ? "Yes" : "No") << '\n';
}
int dfs(int current) {
    scc[current] = id++;
    s.push(current);
    int pid = scc[current];

    for(int next : arr[current]) {
        if(scc[next] == 0) {
            pid = min(pid, dfs(next));
        } else if(!finished[next]) {
            pid = min(pid, scc[next]);
        }
    }

    if(pid == scc[current]) {
        vector<int> resList;
        while(current) {
            int y = s.top(); s.pop();
            resList.push_back(y);
            finished[y] = true;
            if(y == current) {
                break;
            }
        }
        res.push_back(resList);
    }

    return pid;
}