#include "split.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second int n; bool found=0; vector<int> ans, cc, ooga; vector<bool> visited; vector<pii> vect; vector<vector<int> > graph; void label(int node, int p, int t){ if (visited[node])return; if (cc[t]>=vect[t].fi)return; ++cc[t]; ans[node]=vect[t].se; for (auto num:graph[node])if (num!=p)label(num, node, t); } int dfscount(int node){ if (visited[node])return 0; visited[node]=1; ooga.pb(node); int res=1; for (auto num:graph[node])if (!visited[num])res+=dfscount(num); return res; } bool bfs(int start){ stack<int> q; ans.assign(n, 0); int cc=0; q.push(start); visited.assign(n, 0); vector<bool> done(n, 0); while (q.size()&&cc<vect[0].fi){ int node=q.top(); q.pop(); if (ans[node])continue; done[node]=1; visited[node]=1; ans[node]=vect[0].se; ++cc; for (auto num:graph[node])if (!visited[num])q.push(num); } if (cc<vect[0].fi)return 0; bool can=0; for (int i=0; i<n; ++i){ ooga.clear(); if (!done[i]&&!ans[i]&&dfscount(i)>=vect[1].fi){ for (auto a:ooga)done[a]=1, visited[a]=0; label(i, -1, 1), can=1; break; } for (auto a:ooga)done[a]=1, visited[a]=0; } for (int i=0; i<n; ++i)if (!ans[i])ans[i]=vect[2].se; return can; } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q){ n=N; cc.resize(4, 0); vect.pb(mp(a, 1)); vect.pb(mp(b, 2)); vect.pb(mp(c, 3)); sort(vect.begin(), vect.end()); ans.resize(n, 0); graph.resize(n); visited.resize(n, 0); for (int i=0; i<p.size(); ++i){ graph[p[i]].pb(q[i]); graph[q[i]].pb(p[i]); } for (int i=0; i<n; ++i)if (bfs(i))return ans; vector<int> temp(n, 0); return temp; }