글 읽기 - 이 문제가 왜 SCC인가요?

mhkim4886 4년 전 2

첨부한 코드로 AC를 받았습니다.

주어진 점들을 그래프로 보고, 위상 정렬한 후에 그 순서대로 DFS를 돌리면서 해결했습니다.

그런데 SCC의 정의는

방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라 칭합니다.

출처: https://jason9319.tistory.com/98

라고 하는데, 이 문제에서 묶이는 그룹들(문제에 주어진 예제에서는 1 → 2 → 3)은 SCC라고 보기 힘든 것 같아요. 거꾸로는 갈 수 없기 때문입니다. (물론 사이클이 있다면 SCC가 되겠지만요)

문제를 어떻게 해석하면 SCC로 볼 수 있나요?

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tgmath.h>
#include <tuple>
#include <unistd.h>
#include <unordered_map>
#include <vector>
using namespace std;

typedef long long int lli;
typedef pair<int, int> pii;
typedef pair<lli, lli> plli;
typedef unsigned char byte;
typedef unsigned int uint;
typedef unsigned long long int ulli;

void DFS(vector<vector<int>> &G, vector<bool> &visited, vector<int> &st, int curr)
{
    if(visited[curr]) return;
    else visited[curr] = true;
    for(int p : G[curr]) DFS(G, visited, st, p);
    st.push_back(curr);
}

void DFS(vector<vector<int>> &G, vector<bool> &visited, int curr)
{
    if(visited[curr]) return;
    else visited[curr] = true;
    for(int p : G[curr]) DFS(G, visited, p);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while(T --> 0) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> G(n+1);
        vector<bool> visited(n+1);
        vector<int> st;
        for(int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            G[x].push_back(y);
        }

        for(int i = 1; i <= n; i++) {
            DFS(G, visited, st, i);
        }
        reverse(st.begin(), st.end());
        fill(visited.begin(), visited.end(), false);
        int ans = 0;
        for(int k : st) {
            if(!visited[k]) {
                ans++;
                DFS(G, visited, k);
            }
        }
        cout << ans << "\n";
    }
}

djm03178 4년 전 0

1 2 3이 하나의 SCC인 것으로 보는 것은 아니고, 서로 별개의 SCC로 만든 뒤 SCC끼리의 위상 정렬로 푸는 방식입니다. 이 코드와 결국 원리는 같은 것 같네요.

mhkim4886 4년 전 0

그러면 결국 사이클이 없는 것들은 정점 하나짜리 SCC가 되고, 사이클이 있다면 여러 정점이 묶인 SCC가 되는데 이 SCC들을 위상 정렬하는 문제라는 뜻이시죠? 감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 문제가 왜 SCC인가요?

mhkim4886 4년 전 2

djm03178 4년 전 0

mhkim4886 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말