#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, mn=INT_MAX/2; vector<bool> key, visited, die, skip; vector<int> vect, ans, dsu, in, gone; vector<vector<int> > nokey; vector<vector<pii> > graph; int fp(int a){ if (dsu[a]==-1)return a; return dsu[a]=fp(dsu[a]); } void merge(int a, int b){ a=fp(a), b=fp(b); if (a!=b)dsu[a]=b; } void reset(){ for (auto a:in)visited[a]=key[vect[a]]=0; for (auto a:gone)nokey[a].clear(); gone.clear(); in.clear(); } void bfs(int start){ queue<int> q; q.push(start); key[vect[start]]=1; while (q.size()){ int node=q.front(); q.pop(); if (fp(node)!=fp(start)){ skip[node]=1; merge(start, node); reset(); return; } if (visited[node])continue; visited[node]=1; in.pb(node); if (!key[vect[node]]){ for (auto a:nokey[vect[node]])q.push(a); key[vect[node]]=1; } for (auto num:graph[node])if (!visited[num.fi]){ if (key[num.se])q.push(num.fi); else nokey[num.se].pb(num.fi), gone.pb(num.se); } } die[start]=1; if (in.size()<mn)mn=in.size(), ans=in; else if (in.size()==mn)for (auto a:in)ans.pb(a); reset(); } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){ n=r.size(); vect=r; die.resize(n, 0); key.resize(n, 0); visited.resize(n, 0); nokey.resize(n); graph.resize(n); dsu.resize(n, -1); for (int i=0; i<u.size(); ++i){ graph[u[i]].pb(mp(v[i], c[i])); graph[v[i]].pb(mp(u[i], c[i])); } bool loop=1; while (loop){ loop=0; skip.assign(n, 0); for (int i=0; i<n; ++i)if (fp(i)==i&&!die[i]&&!skip[i]){ bfs(i); loop=1; } } for (int i=0; i<n; ++i)bfs(i); vector<int> res(n, 0); for (auto a:ans)res[a]=1; return res; }