fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define str string
  5. #define FOR(i,a,b) for(int i = (a) , _b = (b) ; i <= _b ; i++)
  6. #define FOD(i,a,b) for(int i = (a) , _b = (b) ; i < _b ; i++)
  7. #define REP(i,a,b) for(int i = (a) , _b = (b) ; i >= _b ; i--)
  8. #define RED(i,a,b) for(int i = (a) , _b = (b) ; i > _b ; i--)
  9. #define CL(a,x) memset(a,x,sizeof(a))
  10. #define MASK(x) (1LL << (x))
  11. #define fi first
  12. #define se second
  13. #define pii pair<int,int>
  14. #define pb push_back
  15. #define endl '\n'
  16. #define NAME
  17. using namespace std;
  18. const int N = 1e6 + 7 , MOD = 1e9 + 7;
  19.  
  20. int n, m;
  21. vector<int> a[N];
  22. ll res;
  23. int timeDFS;
  24. ll temp;
  25. int num[N], low[N];
  26. vector<int> bridge_adj[N];
  27. bool check[N];
  28.  
  29. void DFS(int u, int pre = -1){
  30.     num[u] = low[u] = ++timeDFS;
  31.     for(int v : a[u]) if(v != pre){
  32.         if(!num[v]){
  33.             DFS(v, u);
  34.             low[u] = min(low[u], low[v]);
  35.             if(low[v] > num[u]){
  36.                 bridge_adj[u].pb(v);
  37.                 bridge_adj[v].pb(u);
  38.             }
  39.         }
  40.         else low[u] = min(low[u], num[v]);
  41.     }
  42. }
  43.  
  44. void DFS_DAG(int u){
  45.     check[u] = true;
  46.     temp++;
  47.     for(int v : bridge_adj[u])if(!check[v]) DFS_DAG(v);
  48. }
  49.  
  50. void load(){
  51.     FOR(i,1,n) if(!num[i]) DFS(i);
  52.     FOR(i,1,n) if(!check[i]){
  53.         temp = 0;
  54.         DFS_DAG(i);
  55.         if (temp >= 3) {
  56.             res += ((temp - 1) * (temp - 2)) / 2;
  57.         }
  58.     }
  59. }
  60.  
  61. int main(){
  62.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  63.     cin >> n >> m;
  64.     FOR(i,1,m){
  65.         int u, v;cin >> u >> v;
  66.         a[u].pb(v);
  67.         a[v].pb(u);
  68.     }
  69.     load();
  70.     cout << res;
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 52232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/H99TN7
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!