#include "split.h" #include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define fr first #define se second const int MAXN = 1e5 + 10; const int INF = 0x3f3f3f3f; bool seen[MAXN]; int ans[MAXN]; vector<int> adj[MAXN]; bool artpoint[MAXN]; int in[MAXN], low[MAXN]; int t = 0; void dfsArt(int node, int dad) { in[node] = low[node] = ++t; seen[node] = 1; int kids = 0; for (auto u : adj[node]) { if (u == dad) continue; if (seen[u]) low[node] = min(low[node], in[u]); else { dfsArt(u, node); low[node] = min(low[node], low[u]); kids++; if (node == 0) continue; if (low[u] >= in[node]) artpoint[node] = 1; } } if ((node == 0) && kids) artpoint[node] = 1; } int qtd, qual; void dfs(int node) { seen[node] = 1; ans[node] = qual; qtd--; for (auto u : adj[node]) if (!seen[u] && (qtd > 0)) dfs(u); } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { vector<pii> ord = {{a, 1}, {b, 2}, {c, 3}}; sort(ord.begin(), ord.end()); for (int i = 0; i < ((int) p.size()); i++) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } // calc dfsArt(0, -1); int start = 0; for (int i = 0; i < n; i++) if (!artpoint[i]) start = i; memset(seen, 0, sizeof seen); seen[start] = 1; ans[start] = 1; if (start > 0) start = 0; else start = 1; qtd = ord[1].fr; qual = ord[1].se; dfs(start); // retornar vector<int> resposta(n); for (int i = 0; i < n; i++) resposta[i] = ans[i]; for (auto& u : resposta) if (u == 0) u = ord[2].se; return resposta; }