Dang_Quan_10_Tin

HARDDAG

Aug 26th, 2020
291
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <stack>
  8. #include <queue>
  9. #define task ""
  10. using namespace std;
  11. using ll = long long;
  12. using ld = long double;
  13.  
  14. const int N = 15e4 + 2;
  15. const int Inf = 1e9 + 7;
  16. int n, m, l(0), low[N], num[N], cnt(0);
  17. int par[N], x[N], deg[N], pos[N], in[N], out[N];
  18. bool ok[N];
  19. vector<int> adj[N],
  20.     direct[N],
  21.     lt[N],
  22.     st,
  23.     nadj[N];
  24.  
  25. int findpar(int v)
  26. {
  27.     return par[v] < 0 ? v : par[v] = findpar(par[v]);
  28. }
  29.  
  30. void Read()
  31. {
  32.     cin >> n >> m;
  33.     memset(par, -1, sizeof par);
  34.     for (int i = 1; i <= m; ++i)
  35.     {
  36.         int u, v;
  37.         cin >> u >> v;
  38.         int x = findpar(u),
  39.             y = findpar(v);
  40.         if (x != y)
  41.         {
  42.             par[x] += par[y];
  43.             par[y] = x;
  44.         }
  45.         direct[u].push_back(v);
  46.     }
  47. }
  48.  
  49. void dfs(int v)
  50. {
  51.     num[v] = low[v] = ++cnt;
  52.     st.push_back(v);
  53.     for (auto i : direct[v])
  54.         if (num[i])
  55.             low[v] = min(low[v], num[i]);
  56.         else
  57.         {
  58.             dfs(i);
  59.             low[v] = min(low[v], low[i]);
  60.         }
  61.     if (low[v] == num[v])
  62.     {
  63.         ++l;
  64.         int t;
  65.         do
  66.         {
  67.             t = st.back();
  68.             lt[l].push_back(t);
  69.             st.pop_back();
  70.             low[t] = num[t] = Inf;
  71.             par[t] = l;
  72.         } while (v != t);
  73.     }
  74. }
  75.  
  76. void tarjan()
  77. {
  78.     for (int i = 1; i <= n; ++i)
  79.         if (!num[i])
  80.             dfs(i);
  81. }
  82.  
  83. void topoSort()
  84. {
  85.     stack<int> q;
  86.     for (int i = 1; i <= l; ++i)
  87.     {
  88.         deg[i] = nadj[i].size();
  89.         if (deg[i] == 0)
  90.             q.push(i);
  91.     }
  92.     int piv = 0;
  93.     while (q.size())
  94.     {
  95.         x[++piv] = q.top();
  96.         pos[x[piv]] = piv;
  97.         q.pop();
  98.         for (auto i : adj[x[piv]])
  99.         {
  100.             --deg[i];
  101.             if (deg[i] == 0)
  102.                 q.push(i);
  103.         }
  104.     }
  105. }
  106.  
  107. void Solve()
  108. {
  109.     vector<bool> ck(N);
  110.     int check = 0;
  111.     for (int i = 1; i <= n; ++i)
  112.     {
  113.         int v = findpar(i);
  114.         if (!ck[v])
  115.         {
  116.             ++check;
  117.             ck[v] = 1;
  118.         }
  119.     }
  120.     if (check > 1)
  121.     {
  122.         cout << 0;
  123.         return;
  124.     }
  125.     tarjan();
  126.  
  127.     for (int i = 1; i <= n; ++i)
  128.     {
  129.         for (auto j : direct[i])
  130.         {
  131.             if (par[i] != par[j])
  132.             {
  133.                 adj[par[i]].push_back(par[j]);
  134.                 nadj[par[j]].push_back(par[i]);
  135.             }
  136.         }
  137.     }
  138.     for (int i = 1; i <= l; ++i)
  139.     {
  140.         sort(adj[i].begin(), adj[i].end());
  141.         adj[i].resize(unique(adj[i].begin(), adj[i].end()) - adj[i].begin());
  142.         sort(nadj[i].begin(), nadj[i].end());
  143.         nadj[i].resize(unique(nadj[i].begin(), nadj[i].end()) - nadj[i].begin());
  144.         in[i] = nadj[i].size();
  145.         out[i] = adj[i].size();
  146.     }
  147.     topoSort();
  148.     vector<int> a;
  149.     int Lef(0), Rig(0);
  150.     for (int i = 1; i <= l; ++i)
  151.         if (in[x[i]] == 0)
  152.             ++Rig;
  153.     for (int i = 1; i <= l; ++i)
  154.     {
  155.         if (in[x[i]] == 0)
  156.             --Rig;
  157.         for (auto j : nadj[x[i]])
  158.         {
  159.             if (out[j] == 0)
  160.                 --Lef;
  161.             ++out[j];
  162.         }
  163.         if (Lef == 0 && Rig == 0)
  164.         {
  165.             for (auto j : lt[x[i]])
  166.                 a.push_back(j);
  167.         }
  168.         for (auto j : adj[x[i]])
  169.         {
  170.             --in[j];
  171.             --out[x[i]];
  172.             if (in[j] == 0)
  173.                 ++Rig;
  174.         }
  175.         if (out[x[i]] == 0)
  176.             ++Lef;
  177.     }
  178.     sort(a.begin(), a.end());
  179.     cout << a.size() << "\n";
  180.     for (auto i : a)
  181.         cout << i << " ";
  182. }
  183.  
  184. int32_t main()
  185. {
  186.     ios::sync_with_stdio(0);
  187.     cin.tie(0);
  188.     cout.tie(0);
  189.     if (fopen(task ".INP", "r"))
  190.         freopen(task ".INP", "r", stdin),
  191.             freopen(task ".OUT", "w", stdout);
  192.     Read();
  193.     Solve();
  194. }
  195. /*
  196. 5 5
  197. 1 2
  198. 2 3
  199. 3 5
  200. 4 5
  201. 2 4
  202. */
Advertisement
Add Comment
Please, Sign In to add comment