aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTa180m2020-05-03 15:10:42 -0500
committerGitHub2020-05-03 15:10:42 -0500
commit51e730f351f28ef2e798c97dae20b11a8b71542d (patch)
tree132da8fe63428a1bf7f6df4eb238e30ef1db797c
parent1ed1261e189fcb1532aea13bf654a62101bde4c9 (diff)
Create fcolor.cpp
-rw-r--r--2020/US Open/Gold/fcolor.cpp38
1 files changed, 38 insertions, 0 deletions
diff --git a/2020/US Open/Gold/fcolor.cpp b/2020/US Open/Gold/fcolor.cpp
new file mode 100644
index 0000000..4bf342a
--- /dev/null
+++ b/2020/US Open/Gold/fcolor.cpp
@@ -0,0 +1,38 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int cnt = 0, c[200002], p[200002], ans[200002];
+bitset<200002> vis;
+vector<int> G[200002], H[200002];
+
+void dfs(int u) {
+ vis[u] = 1;
+ for (auto& v : G[u]) {
+ if (!vis[v]) dfs(v);
+ if (c[v]) c[u] = max(p[c[v]], c[u]);
+ }
+ for (auto& v : H[u]) {
+ if (!vis[v]) dfs(v);
+ if (c[u]) c[v] = max(p[c[u]], c[v]);
+ }
+ if (!c[u]) c[u] = ++cnt;
+ for (auto& v : G[u]) if (c[v]) p[c[v]] = max(c[u], p[c[v]]);
+ for (auto& v : H[u]) if (c[v]) p[c[u]] = max(c[v], p[c[u]]);
+}
+
+int main() {
+ ifstream cin("fcolor.in");
+ ofstream cout("fcolor.out");
+
+ int N, M; cin >> N >> M;
+ while (M--) {
+ int a, b; cin >> a >> b;
+ G[b].push_back(a), H[a].push_back(b);
+ }
+ for (int u = 1; u <= N; ++u) dfs(u);
+ for (int u = 1; u <= N; ++u) dfs(u);
+ for (int u = 1; u <= N; ++u) dfs(u);
+ cnt = 0;
+ for (int u = 1; u <= N; ++u) if (!ans[c[u]]) ans[c[u]] = ++cnt;
+ for (int u = 1; u <= N; ++u) cout << ans[c[u]] << '\n';
+}