fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pub push_back
  3. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  4. #define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
  5. #define pii pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define int long long
  9. using namespace std;
  10.  
  11. const int N = 5e5 + 5;
  12. const int M = 350;
  13. const int LOG = 19;
  14. const int inf = 3e18;
  15.  
  16. int n, m;
  17.  
  18. int scc = 0, cnt = 0;
  19. int vis[N], low[N], id[N], del[N];
  20. int cc[N], sz[N];
  21. int in[N], out[N];
  22.  
  23. stack <int> st;
  24. vector <int> a[N];
  25. vector <pii> edge;
  26.  
  27. void tarjan(int u) {
  28.     vis[u] = 1;
  29.     low[u] = id[u] = ++cnt;
  30.     st.push(u);
  31.     for(int v : a[u]) {
  32.         if (del[v]) continue;
  33.         if (!vis[v]) {
  34.             tarjan(v);
  35.             low[u] = min(low[u], low[v]);
  36.         }
  37.         else low[u] = min(low[u], id[v]);
  38.     }
  39.     if (low[u] == id[u]) {
  40.         scc ++;
  41.         int v;
  42.         do {
  43.             v = st.top(); st.pop();
  44.             del[v] = 1;
  45.             cc[v] = scc;
  46.             sz[scc] ++;
  47.         } while(u != v);
  48.     }
  49. }
  50. void solve() {
  51.     cin >> n >> m;
  52.     FOR(i, 1, m, 1) {
  53.         int u, v;
  54.         cin >> u >> v;
  55.         a[u].pub(v);
  56.         edge.pub({u, v});
  57.     }
  58.  
  59.     FOR(i, 1, n, 1) if (!vis[i]) tarjan(i);
  60.  
  61.     for(pii x : edge) {
  62.         int u = cc[x.fi];
  63.         int v = cc[x.se];
  64.         if (u != v) {
  65.             in[v] ++;
  66.             out[u] ++;
  67.         }
  68.     }
  69.  
  70.     int cnt = 0;
  71.     int ans = 0;
  72.  
  73.     FOR(i, 1, n, 1) {
  74.         if (!out[i]) {
  75.             cnt ++;
  76.             if (cnt == 2) {
  77.                 return (void)(cout << 0 << '\n');
  78.             }
  79.             ans += sz[i];
  80.         }
  81.     }
  82.     cout << ans << '\n';
  83. }
  84. signed main() {
  85.     #define name "baitap"
  86.     if (ifstream(name".inp")) {
  87.         freopen(name".inp", "r", stdin);
  88.         freopen(name".out", "w", stdout);
  89.     }
  90.  
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(0);
  93.     cout.tie(0);
  94.  
  95.     solve();
  96. }
Success #stdin #stdout 0.01s 16516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/86yZKz
language:
C++ (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!