Advertisement
Guest User

Untitled

a guest
Jul 24th, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. vector < vector <ll> > adj(801);
  7. stack <ll> st;
  8. ll n, m, cnt = 0, res = 0, number[801], low[801];
  9. bool fr[801];
  10.  
  11. void dfs(ll u) {
  12.     number[u] = low[u] = cnt++;
  13.     st.push(u);
  14.     for (int i = 0; i < adj[u].size(); i++)
  15.         if (fr[adj[u][i]]) {
  16.             if (number[adj[u][i]]) low[u] = min(low[u], number[adj[u][i]]);
  17.             else {
  18.                 dfs(adj[u][i]);
  19.                 low[u] = min(low[u], low[adj[u][i]]);
  20.             }
  21.         }
  22.     if (number[u] == low[u]) {
  23.         res++;
  24.         ll v = st.top();
  25.         st.pop();
  26.         fr[v] = false;
  27.         while (v != u) {
  28.             cout << v << " ";
  29.             v = st.top();
  30.             st.pop();
  31.             fr[v] = false;
  32.         }
  33.         cout << u << endl;
  34.     }
  35. }
  36.  
  37. int main() {
  38.     freopen("test.inp", "r", stdin);
  39.     freopen("test.out", "w", stdout);
  40.     cin >> n >> m;
  41.     for (int i = 1; i <= m; i++) {
  42.         ll u, v;
  43.         cin >> u >> v;
  44.         adj[u].push_back(v);
  45.     }
  46.     memset(fr, true, sizeof(fr));
  47.     for (int i = 1; i <= m; i++)
  48.         if (fr[i]) dfs(i);
  49.     cout << res;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement