#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
ostream& operator<< (ostream& os, const pair<T, U> &pair) {
return os << '(' << pair.first << ", " << pair.second << ')';
}
template<class T>
ostream& operator<< (ostream& os, const vector<T> &arr) {
os << '[';
for (const T &v : arr) os << v << ", ";
return os << ']';
}
// return a partial partition of {0, ..., n-1} corresponding to sccs that cannot reach any other nodes
vector<vector<int>> partial_sccs(const vector<int> &keys, const vector<vector<pair<int, int>>> &graph) {
int n = keys.size();
vector<vector<int>> ans;
// finalized[i] = can this vtx currently reach a vtx in ans?
vector<bool> finalized(n);
vector<int> cstack;
vector<int> stack_pos(n, -1);
vector<int> lowest_on_stack(n, -1);
// INVARIANT: If we haven't finalized this, every node on the stack
// can reach some higher up node.
vector<vector<int>> next_vertex_queue(n);
vector<vector<pair<int, int>>> pending_color_queue(n);
auto mark_vertex = [&] (int c) {
for (auto &[from, to] : pending_color_queue[c]) {
next_vertex_queue[from].push_back(to);
}
pending_color_queue[c].clear();
};
auto register_edge = [&] (int from, int to, int c) {
pending_color_queue[c].emplace_back(from, to);
};
function<bool(int)> visit; visit = [&] (int i) { // return value: is this not finalized yet?
if (finalized[i]) return false;
/*
cerr << "visit " << i << endl;
cerr << cstack << endl;
cerr << stack_pos << endl;
cerr << lowest_on_stack << endl;
*/
stack_pos[i] = cstack.size();
cstack.push_back(i);
lowest_on_stack[keys[i]] = stack_pos[i];
int highest_stack_point = n; // WE WILL SET THIS LATER!
// need to find edges to traverse, to update highest_stack_point, and to make recursive calls
mark_vertex(keys[i]);
vector<pair<int, int>> neighbors = graph[i];
for (auto [to, c] : neighbors) register_edge(i, to, c);
sort(begin(neighbors), end(neighbors), [&] (pair<int, int> a, pair<int, int> b) {
return lowest_on_stack[a.second] < lowest_on_stack[b.second];
});
// cerr << neighbors << endl;
auto update_hsp = [&] (int stack_point) {
highest_stack_point = min(highest_stack_point, stack_point);
while (!neighbors.empty() && lowest_on_stack[neighbors.back().second] >= highest_stack_point) {
next_vertex_queue[i].push_back(neighbors.back().first);
neighbors.pop_back();
}
};
auto traverse_edge = [&] (int to) {
if (stack_pos[to] != -1) {
update_hsp(stack_pos[to]);
return true;
} else {
return visit(to);
}
};
update_hsp(stack_pos[i]);
while (!next_vertex_queue[i].empty()) {
int v = next_vertex_queue[i].back(); next_vertex_queue[i].pop_back();
if (!traverse_edge(v)) return false;
}
cerr << "visit " << i << " end HSP " << highest_stack_point << endl;
if (highest_stack_point >= stack_pos[i]) {
// we've found a new SCC, add to the answer.
// we will clean up later, for now, mark all vtxs here as finalized
ans.emplace_back(begin(cstack) + stack_pos[i], end(cstack));
for (int v : cstack) finalized[v] = true;
return false;
} else {
return true;
}
};
for (int i = 0; i < n; ++i) {
if (!finalized[i]) {
visit(i);
// clean up the stack
for (int v : cstack) {
stack_pos[v] = -1;
lowest_on_stack[keys[v]] = -1;
}
}
}
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size(), m = u.size();
vector<vector<pair<int, int>>> graph(n);
for (int i = 0; i < m; ++i) {
graph[u[i]].emplace_back(v[i], c[i]);
graph[v[i]].emplace_back(u[i], c[i]);
}
vector<vector<int>> sccs = partial_sccs(r, graph);
int min_scc_size = n;
for (auto &scc : sccs) min_scc_size = min((int)scc.size(), min_scc_size);
vector<int> ans(n);
for (auto &scc : sccs) {
if (scc.size() == min_scc_size) {
for (int v : scc) ans[v] = 1;
}
}
return ans;
}
