Advertisement
Guest User

Untitled

a guest
Dec 6th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <utility>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <queue>
  9. #include <stack>
  10. #include <string>
  11. #include <cmath>
  12. #include <bitset>
  13. #include <ctime>
  14. #include <random>
  15. #include <cstdlib>
  16. #include <deque>
  17. #define F first
  18. #define S second
  19. #define pb push_back
  20. #define ll long long
  21.  
  22. using namespace std;
  23.  
  24. const int N = 2e5+5, INF = 1e9;
  25. const bool debug = 0;
  26.  
  27. int n, m, a[N], b[N], tin[N], tk;
  28. ll ans;
  29. vector<int> g[N];
  30. bool ban[N], u[N];
  31.  
  32. int dfs(int v, int p = 0){
  33.     int res = tin[v] = ++tk, go;
  34.     for(int to: g[v]){
  35.         go = a[to]^b[to]^v;
  36.         if(go==p) continue;
  37.         if(tin[go]){ res = min(res,tin[go]); continue;}
  38.         int temp = dfs(go,v);
  39.         res = min(temp,res);
  40.         if(temp>=tin[go]) ban[to] = 1;
  41.     }
  42.     return res;
  43. }
  44.  
  45. int dfs2(int v){
  46.     if(u[v]) return 0;
  47.     int res = u[v] = 1;
  48.     for(int i = 0; i < g[v].size(); ++i){
  49.         if(!ban[g[v][i]]) continue;
  50.         res+=dfs2(a[g[v][i]]^b[g[v][i]]^v);
  51.     }
  52.     return res;
  53. }
  54.  
  55. int main(){
  56.     if(debug) freopen("input.txt","r",stdin);
  57.     ios_base::sync_with_stdio(0);
  58.     cin.tie(0); cout.tie(0);
  59.  
  60.     cin >> n >> m;
  61.  
  62.     for(int i = 1; i <= m; ++i)
  63.         cin >> a[i] >> b[i],
  64.         g[a[i]].pb(i),
  65.         g[b[i]].pb(i);
  66.     for(int i = 1; i <= n; ++i)
  67.         if(!tin[i]) dfs(i);
  68.     for(int i = 1; i <= n; ++i){
  69.         ll temp = max(1,dfs2(i));
  70.         ans += temp*(temp-1)/2-temp+1;
  71.     }
  72.     cout << ans;
  73.  
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement