백준 1432 - 그래프 수정

그래프 수정

풀이

위상정렬을 반대로 하면 풀리는 문제다.

1. 방향 그래프를 반대로 한다.
2. 사이클 검사를 한다. 사이클이 있다면 불가능하므로 -1을 출력한다.
3. 반대 그래프로 위상정렬을 하는데, 우선순위 큐를 이용해서 숫자가 클수록 먼저 방문한다.

3번의 이유는 반대로 방문하는 것이므로 order 가 n 부터 시작하므로 숫자가 큰 걸 먼저 방문한다는 것은 원래대로 방문이 숫자가 작은 노드일수록 최대한 먼저 방문한다는 의미다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, a, b) for(ll i=(a); i<(b); i++)
#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define Bor(i, a, b) for(ll i=(a); i>(b); i--)
#define BOR(i, a, b) for(ll i=(a); i>=(b); i--)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

int n;
vector<vector<int>> r;
vector<int> ans, indeg;

vector<bool> vis, rec;
bool cycle(int u) {
    if(!vis[u]) {
        vis[u] = true;
        rec[u] = true;

        for(int v : r[u]) {
            if(!vis[v] and cycle(v)) return true;
            else if(rec[v]) return true;
        }
    }
    rec[u] = false;
    return false;
}

void topological_sort() {
    priority_queue<int> pq;
    fill(all(vis), false);
    FOR(i,1,n) {
        if(indeg[i] == 0) {
            vis[i] = true;
            pq.push(i);
        }
    }

    int order=n;
    while(!pq.empty()) {
        int u = pq.top(); pq.pop();
        ans[u] = order--;
        for(int v : r[u]) {
            if(--indeg[v] != 0) continue;
            if(vis[v]) continue;
            vis[v] = true;
            pq.push(v);
        }
    }
}

void solve() {
    cin >> n;
    r = vector<vector<int>>(n+1);
    ans = vector<int>(n+1, -1);
    indeg = vector<int>(n+1, 0);

    FOR(i,1,n) {
        string s; cin >> s;
        FOR(j,1,n) {
            if(s[j-1] == '1') {
                r[j].push_back(i);
                indeg[i]++;
            }
        }
    }

    vis = vector<bool>(n+1, false);
    rec = vector<bool>(n+1, false);
    FOR(i,1,n) {
        if(cycle(i)) {
            cout << "-1\n";
            return;
        }
    }

    topological_sort();
    FOR(i,1,n) cout << ans[i] << ' ';
    cout << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int TC=1;
//    cin >> TC;
    FOR(tc, 1, TC) {
//        cout << "Case #" << tc << ": ";
        solve();
    }


    return 0;
}