diff options
author | Ta180m | 2020-05-03 15:10:42 -0500 |
---|---|---|
committer | GitHub | 2020-05-03 15:10:42 -0500 |
commit | 51e730f351f28ef2e798c97dae20b11a8b71542d (patch) | |
tree | 132da8fe63428a1bf7f6df4eb238e30ef1db797c | |
parent | 1ed1261e189fcb1532aea13bf654a62101bde4c9 (diff) |
Create fcolor.cpp
-rw-r--r-- | 2020/US Open/Gold/fcolor.cpp | 38 |
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'; +} |