문제

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


알고리즘

SCC


풀이

처음에 문제만 읽어서는 SCC라는 것을 알아채기가 힘들었던 문제입니다. 감이 잡히지 않으므로 2번 예제를 직접 그려보도록 합시다.

그림을 그려본다면 답에 해당하는 간선이 두 가지 종류임을 알 수 있습니다. 첫 번째는 하나의 SCC에서 다른 SCC를 잇는 외부 간선입니다. 두 번째는 각각의 SCC내부를 잇는 내부간선입니다. 이제 각각의 처리방법에 대해 생각해봅시다.

SCC알고리즘의 작동방식을 생각해본다면 하나의 컴포넌트로 묶을 때 스택에서 차례대로 하나씩 꺼낸 후 묶는 것을 알 수 있습니다. 즉 스택에서 연속된 값은 서로를 잇는 내부 간선들임을 알 수 있습니다. 즉 스택에서 꺼내며 $sccid$를 부여 할 때 내부간선을 처리하면 됩니다. 스택의 처음 부분과 하나의 컴포넌트로 묶이는 마지막 부분은 따로 처리를 해줍시다.

외부 간선은 이전의 문제들에서 했던 것처럼, 모든 간선들을 검사하며 하나의 간선을 이루는 양쪽 정점의 $sccid$가 다르다면 외부 간선으로 판단하고 $ans$에 추가해줍시다.

위와 같이 풀게되면 틀리게 됩니다. 그 이유는 각각의 정점 A, B, C에서 A에서 B로, B에서 C를 잇는 간선이 있고 A에서 C를 잇는 간선이 있을 때 필요 없는 A-C 간선을 답에 넣기 때문입니다. 이 간선은 다른 간선들(A-B, B-C)을 통해 가는 경로가 있으므로 최소의 도로망을 만족하지 못하게 됩니다. 이를 플로이드-와샬 알고리즘을 통해 필요 없는 간선을 제거한 후 위 과정을 진행하면 됩니다. 시간 복잡도는 $O(N^3+V+E)$입니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef pair<int, int> pii;

int tc, N, SC, VC;
char x;

vector<vector<int>> adj;
vector<int> discovered, sccid;
stack<int> st;
vector<pii> ans;
int board[300][300];

int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);

    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        int prv = -1;
        for (int i = 0;;++i) {
            int t = st.top();
            st.pop();
            sccid[t] = SC;

            if (i == 0 && here != t) ans.emplace_back(here, t);
            else if (i != 0)ans.emplace_back(prv, t);
            prv = t;

            if (t == here) break;
        }
        ++SC;
    }
    return ret;
}

int main() {
    FAST;
    cin >> tc;
    while (tc--) {
        cin >> N;
        ans.clear();
        adj.clear();
        adj.resize(N);
        discovered.clear(); sccid.clear();
        memset(board, 0, sizeof(board));
        SC = VC = 0;

        rep(i, N) rep(j, N) {
            cin >> x;
            if (x == '1') board[i][j] = 1;
            if (i == j) board[i][j] = 0;
        }

        rep(k, N) rep(i, N) rep(j, N) {
            if (board[i][k] && board[k][j] && board[i][j])
                board[i][j] = 0;
        }

        rep(i, N) rep(j, N) {
            if (board[i][j]) adj[i].emplace_back(j);
        }

        discovered = sccid = vector<int>(N, -1);
        rep(i, N) if (discovered[i] == -1) scc(i);

        rep(here, N) for (auto there : adj[here]) {
            if (sccid[here] != sccid[there]) {
                ans.emplace_back(here, there);
            }
        }
        cout << ans.size() << '\n';

        for (auto [a, b] : ans)
            cout << a + 1 << ' ' << b + 1 << '\n';
        cout << '\n';
    }
    return 0;
}