fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define F first
  5. #define S second
  6. #define Tsetso ios_base::sync_with_stdio(0) ; cin.tie(0) ;
  7. #define Read freopen("minmax.in","r",stdin);
  8. #define matrix vector<vector<ll>>
  9. using namespace std;
  10. const int N = 2e3+50;
  11. int n , dfn[N],lowlink[N] , dfnid , ans;
  12. vector < int > g[N];
  13. void dfs( int node , int par )
  14. {
  15.     dfn[node] = lowlink[node] = ++dfnid;
  16.     int cnt = 0 , ok = 0;
  17.     for ( auto child : g[node])
  18.     {
  19.         if ( child == par)
  20.             continue;
  21.         if (!dfn[child])
  22.         {
  23.             dfs(child,node);
  24.             lowlink[node] = min(lowlink[node],lowlink[child]);
  25.             if ( lowlink[child] >= dfn[node] && par != -1)
  26.                 ok = 1 ;
  27.             ++cnt;
  28.         }
  29.         else
  30.             lowlink[node] = min(lowlink[node],lowlink[child]);
  31.     }
  32.     if ( par == -1 && cnt > 1)
  33.             ok = 1 ;
  34.     ans += ok ;
  35. }
  36.  
  37. int  main(){
  38.     Tsetso
  39.     while (cin >> n && n) {
  40.         string str = "11";
  41.         cin.ignore();
  42.         dfnid = 0;
  43.         for ( int i = 1 ; i <= n ; i++)
  44.             g[i].clear(),dfn[i] = 0;
  45.         getline(cin,str);
  46.         while( str.size() != 1 || str[0] != '0' )
  47.         {
  48.             vector < int > v ;
  49.             str.push_back(' ');
  50.             int res = 0 ;
  51.             for ( int i = 0 ; i < str.size() ; i++)
  52.             {
  53.                 if (str[i] != ' ')
  54.                     res *= 10 , res += str[i] - '0';
  55.                 else if (res)
  56.                     v.push_back(res),res = 0 ;
  57.             }
  58.             for ( int i = 1 ; i < v.size() ; i++)
  59.                     g[v[0]].push_back(v[i]),g[v[i]].push_back(v[0]);
  60.             getline(cin,str);
  61.         }
  62.         for ( int i = 1 ; i <= n ; i++)
  63.                 if (!dfn[i])
  64.                         dfs(i,-1);
  65.         cout << ans << '\n';
  66.         ans = 0 ;
  67.     }
  68. }
Success #stdin #stdout 0s 5640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gOoDzm
language:
C++ (gcc 8.3)
created:
2 years 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!