aboutsummaryrefslogtreecommitdiff
path: root/19/day2/themepark.cpp
diff options
context:
space:
mode:
Diffstat (limited to '19/day2/themepark.cpp')
-rw-r--r--19/day2/themepark.cpp42
1 files changed, 42 insertions, 0 deletions
diff --git a/19/day2/themepark.cpp b/19/day2/themepark.cpp
new file mode 100644
index 0000000..2582eb3
--- /dev/null
+++ b/19/day2/themepark.cpp
@@ -0,0 +1,42 @@
+#include <bits/stdc++.h>
+using namespace std;
+constexpr int MAXN = 100001;
+
+int c[MAXN];
+vector<int> G[MAXN];
+
+int cnt, scc_num, scc[MAXN], in[MAXN], low[MAXN];
+stack<int> s;
+bitset<MAXN> ins;
+
+void tarjan(int u) {
+ low[u] = in[u] = cnt++;
+ s.push(u);
+ ins[u] = 1;
+ for (int v : G[u]) {
+ if (in[v] == -1) tarjan(v), low[u] = min(low[u], low[v]);
+ else if (ins[v]) low[u] = min(low[u], in[v]);
+ }
+ if (low[u] == in[u]) {
+ ++scc_num;
+ while (1) {
+ int x = s.top(); s.pop();
+ scc[x] = scc_num, ins[x] = 0;
+ if (x == u) break;
+ }
+ }
+}
+
+int main() {
+ int N, M, K; cin >> N >> M >> K;
+ while (M--) {
+ int a, b; cin >> a >> b;
+ G[a].push_back(b);
+ }
+
+ memset(scc, -1, sizeof scc), memset(in, -1, sizeof in);
+ for (int u = 1; u <= N; ++u) if (scc[u] == -1) tarjan(u);
+
+ if (scc_num < K) cout << "impossible\n";
+ else for (int u = 1; u <= N; ++u) cout << min(scc[u], K) << '\n';
+} \ No newline at end of file