fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define int long long
  5. const int MAXN = 1e5 + 7;
  6. int low[MAXN], id[MAXN], dfstime, scc[MAXN], cnt, ans, save[MAXN], node[MAXN];
  7. int n, m;
  8. bool mark[MAXN];
  9. vector <int> a[MAXN];
  10. set <int> s[MAXN];
  11. stack <int>st;
  12. void dfs(int u){
  13.     low[u] = id[u] = ++dfstime;
  14.     st.push(u);
  15.     for(auto v : a[u]){
  16.         if(!mark[v]){
  17.             if(!id[v]){
  18.                 dfs(v);
  19.                 low[u] = min(low[v], low[u]);
  20.             }
  21.             else low[u] = min(low[u], id[v]);
  22.         }
  23.     }
  24.     if(low[u] == id[u]){
  25.         int v;
  26.         cnt++;
  27.         do{
  28.             v = st.top();
  29.             st.pop();
  30.             scc[v] = cnt;
  31.             mark[v] = 1;
  32.             node[cnt]++;
  33.         }while(u != v);
  34.     }
  35. }
  36.  
  37. signed main(){
  38.     ios_base::sync_with_stdio(0);
  39.     cout.tie(0);
  40.     cin.tie(0);
  41.     cin >> n >> m;
  42.     for(int i = 1; i <= m; i++){
  43.         int x, y;
  44.         cin >> x >> y;
  45.         if(s[x].find(y) == s[x].end()){
  46.             a[x].push_back(y);
  47.             s[x].insert(y);
  48.         }
  49.     }
  50.     for(int i = 1; i <= n; i++) if(!id[i])dfs(i);
  51.  
  52.     for(int u = 1; u <= n; u++)
  53.         for(auto v : a[u])
  54.             if(scc[u] == scc[v]) save[scc[v]]++;
  55.  
  56.     for(int i = 1; i <= cnt; i++){
  57.         int cur = node[i];
  58.         cur = (cur * (cur - 1));
  59.         ans += cur - save[i];
  60.     }
  61.     cout << ans;
  62. }
Success #stdin #stdout 0.01s 11532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VEMdQD
language:
C++14 (gcc 8.3)
created:
5 days 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!