Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- using pii = pair<int, int>;
- mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
- template <typename T1, typename T2>
- ostream& operator <<(ostream& out, pair<T1, T2> &p) {
- out << '{' << p.first << ", " << p.second << '}';
- return out;
- }
- template <typename T>
- ostream& operator <<(ostream& out, set<T> &s) {
- for (auto &x : s)
- out << x << ' ';
- return out;
- }
- template <typename T>
- ostream& operator <<(ostream &out, multiset<T> &s) {
- for (auto &x : s)
- out << x << ' ';
- return out;
- }
- template <typename T>
- bool ckmin(T &a, T b) {
- return (a > b ? a = b, true : false);
- }
- template <typename T>
- bool ckmax(T &a, T b) {
- return (a < b ? a = b, true : false);
- }
- template <typename T>
- ostream& operator <<(ostream& out, vector<T> &v) {
- for (auto &x : v)
- cout << x << ' ';
- return out;
- }
- void visit(vector<vector<int>> &g, vector<char> &vis, int v) {
- vis[v] = 1;
- for (auto &u : g[v]) {
- if (!vis[u])
- visit(g, vis, u);
- }
- }
- bool check_comp(vector<vector<int>> &g) {
- vector<vector<int>> g_unor((int)g.size());
- for (int v = 0; v < (int)g.size(); ++v) {
- for (auto &u : g[v]) {
- g_unor[v].push_back(u);
- g_unor[u].push_back(v);
- }
- }
- vector<char> vis((int)g.size());
- visit(g_unor, vis, 0);
- return count(vis.begin(), vis.end(), 1) == (int)g.size();
- }
- bool ts_dfs(vector<vector<int>> &g, vector<char> &vis, int v, vector<int> &ts) {
- vis[v] = 1;
- for (auto &u : g[v]) {
- if (vis[u] == 1) {
- return false;
- }
- if (!vis[u]) {
- if (!ts_dfs(g, vis, u, ts))
- return false;
- }
- }
- vis[v] = 2;
- ts.push_back(v);
- return true;
- }
- vector<int> topsort(vector<vector<int>> &g) {
- int n = (int)g.size();
- vector<char> vis(n);
- vector<int> ts;
- for (int i = 0; i < n; ++i) {
- if (!vis[i]) {
- if (!ts_dfs(g, vis, i, ts)) {
- return {};
- }
- }
- }
- reverse(ts.begin(), ts.end());
- return ts;
- }
- vector<int> clear_edges(vector<int> &ts, vector<vector<int>> &g, vector<int> &tin, vector<int> &tout) {
- int n = (int)g.size();
- vector<vector<int>> ng(n);
- vector<int> last(n, -1);
- for (auto &v : ts) {
- for (auto &u : g[v]) {
- if (last[u] != -1) {
- if (!(tin[last[u]] < tin[v] && tout[last[u]] > tout[v])) {
- cout << "No\n";
- exit(0);
- }
- }
- last[u] = v;
- }
- }
- for (int v = 0; v < n; ++v) {
- if (last[v] == -1) continue;
- ng[last[v]].push_back(v);
- }
- g = ng;
- return last;
- }
- void time_dfs(vector<vector<int>> &g, vector<char> &vis, int v, vector<int> &tin, vector<int> &tout, int &cur) {
- vis[v] = 1;
- tin[v] = cur++;
- for (auto &u : g[v]) {
- if (!vis[u])
- time_dfs(g, vis, u, tin, tout, cur);
- }
- tout[v] = cur++;
- }
- bool check_time(vector<vector<int>> &g, vector<char> &vis, int v, vector<int> &tin, vector<int> &tout) {
- vis[v] = 1;
- for (auto &u : g[v]) {
- if (!(tin[v] < tin[u] && tout[v] > tout[u]))
- return false;
- if (!vis[u]) {
- if (!check_time(g, vis, u, tin, tout))
- return false;
- }
- }
- return true;
- }
- void solve() {
- int n, m;
- cin >> n >> m;
- map<pii, char> used;
- vector<vector<int>> g(n);
- for (int i = 0; i < m; ++i) {
- int v, u;
- cin >> v >> u, --v, --u;
- if (!used[{v, u}]) {
- g[v].push_back(u);
- used[{v, u}] = 1;
- }
- }
- if (!check_comp(g)) {
- cout << "No\n";
- return;
- }
- vector<int> ts = topsort(g);
- if (ts.empty()) {
- cout << "No\n";
- return;
- }
- vector<char> vis(n);
- vector<int> tin(n), tout(n);
- int cur = 0;
- time_dfs(g, vis, ts[0], tin, tout, cur);
- vector<int> ans = clear_edges(ts, g, tin, tout);
- fill(vis.begin(), vis.end(), 0);
- visit(g, vis, ts[0]);
- if ((int)count(vis.begin(), vis.end(), 1) != n) {
- cout << "No\n";
- return;
- }
- cout << "Yes\n";
- for (auto &x : ans) {
- if (x == -1)
- cout << -1 << ' ';
- else
- cout << x + 1 << ' ';
- }
- cout << '\n';
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout << fixed << setprecision(9);
- int t = 1;
- //cin >> t;
- while (t--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement