백준 1432 - 그래프 수정
Updated:
Categories: Problem Solving
그래프 수정
풀이
위상정렬을 반대로 하면 풀리는 문제다.
- 방향 그래프를 반대로 한다.
- 사이클 검사를 한다. 사이클이 있다면 불가능하므로 -1을 출력한다.
- 반대 그래프로 위상정렬을 하는데, 우선순위 큐를 이용해서 숫자가 클수록 먼저 방문한다.
3번의 이유는 반대로 방문하는 것이므로 order 가 n 부터 시작하므로 숫자가 큰 걸 먼저 방문한다는 것은 원래대로 방문이 숫자가 작은 노드일수록 최대한 먼저 방문한다는 의미다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#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;
}
Leave a comment