fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. #define fi first
  5. #define se second
  6. #define endl '\n'
  7. #define lb long double
  8.  
  9. #define vi std::vector<int>
  10. #define isz(v) (int) v.size()
  11. #define pii std::pair<int, int>
  12. #define all(v) v.begin(), v.end()
  13. #define vii vector<pair<int, int>>
  14.  
  15. #define loop cerr << "here" << endl;
  16. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  17.  
  18. using namespace std;
  19. typedef long long ll;
  20.  
  21. const int MAXN = 2e5 + 7;
  22. const int inf32 = 1e15;
  23.  
  24. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  25. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  26.  
  27. stack<int> st;
  28. int dfstimer, id[MAXN], low[MAXN], n, sccCnt, scc[MAXN], sz[MAXN];
  29. vi a[MAXN];
  30. bool articulation_point[MAXN];
  31. vii edge;
  32.  
  33. void dfsTarjan(int u, int p){
  34.     id[u] = low[u] = ++dfstimer;
  35.     st.push(u);
  36.     int cnt = (u != 1);
  37.  
  38.     for(auto v : a[u]){
  39.         if(v == p) continue;
  40.         if(id[v]){
  41.             minimize(low[u], id[v]);
  42.         }
  43.  
  44.         else{
  45.             dfsTarjan(v, u);
  46.             minimize(low[u], low[v]);
  47.             if(low[v] >= id[u]) cnt++;
  48.         }
  49.  
  50.     }
  51.  
  52.  
  53.     if(low[u] == id[u]){
  54.         int v;
  55.         sccCnt++;
  56.  
  57.         do{
  58.             sz[sccCnt]++;
  59.             v = st.top();
  60.             st.pop();
  61.             scc[v] = sccCnt;
  62.  
  63.         }while(v != u);
  64.     }
  65.  
  66. }
  67.  
  68. bool check(int u, int v){
  69.     if(sz[scc[u]] > 1){
  70.         if(scc[u] == scc[v] and (isz(a[u]) > 2 or isz(a[v]) > 2)){
  71.             return 1;
  72.         }
  73.         else if(scc[u] != scc[v] and (isz(a[u]) > 3 or isz(a[v]) > 1)){
  74.                 return 1;
  75.         }
  76.         return 0;
  77.     }
  78.     if(isz(a[u]) == 1){
  79.         if(sz[scc[v]] > 1 and isz(a[v]) > 3) return 1;
  80.         else if(sz[scc[v]] == 1 and isz(a[v]) > 2) return 1;
  81.     }
  82.     else{
  83.         return isz(a[u]) > 1 and isz(a[v]) > 1 ;
  84.     }
  85.     return 0;
  86. }
  87.  
  88. signed main(){
  89.     ios::sync_with_stdio(false);
  90.     cin.tie(nullptr);
  91.     #define task "bai3"
  92.     if (fopen(task".inp", "r")){
  93.         freopen(task".inp", "r", stdin);
  94.         freopen(task".out", "w", stdout);
  95.     }
  96.  
  97.     cin >> n;
  98.     for(int i = 1; i <= n; i++){
  99.         int x, y;
  100.         cin >> x >> y;
  101.         a[x].push_back(y);
  102.         a[y].push_back(x);
  103.         edge.push_back({x, y});
  104.     }
  105.  
  106.     dfsTarjan(1, -1);
  107.  
  108.     int ans = 0;
  109.     for(auto i : edge){
  110.         int u = i.fi, v = i.se;
  111.         ans += check(u, v) | check(v, u);
  112.     }
  113.  
  114.     cout << ans;
  115. }
  116.  
Success #stdin #stdout 0.01s 10524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3CxvFG
language:
C++14 (gcc 8.3)
created:
4 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!