Insyder01

Untitled

Apr 12th, 2017
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define L(i, m, n) for(int i(m);i < n;i++)
  3. #define pb push_back
  4. #define D(X) cout<<"  "<<#X": "<<X<<endl;
  5. #define in(x) cin >> x
  6. #define SZ(X) int(X.size())
  7. #define clr(A, V) L(i, 0, SZ(A) A[i]=V
  8. #define ff first
  9. #define ss second
  10. #define RF(X) freopen(X, "r", stdin)
  11. #define WF(X) freopen(X, "w", stdout)
  12. using namespace std;
  13. typedef long long ll;
  14. typedef pair<ll,ll> pll;
  15. typedef vector<int> vi;
  16. typedef vector<vi> vii;
  17. typedef pair<int,int> pii;
  18. typedef vector<pii> vpii;
  19. typedef pair<int, string> pis;
  20. typedef vector<string> vs;
  21. typedef pair<pair<int, int>, pair<int, int > > piiii;
  22. const int MAXX=105;
  23. bool vis[MAXX],AP[MAXX];
  24. int parent[MAXX],low[MAXX],disc[MAXX];
  25. int tim=0;
  26. vii adj(MAXX,vi());
  27. void init(){
  28.     L(i,0,MAXX){
  29.         vis[i]=AP[i]=0;parent[i]=-1;
  30.         adj[i].clear();
  31.         low[i]=0;
  32.     }
  33.     tim=0;
  34. }
  35. void dfs(int u){
  36.     vis[u]=1;
  37.     low[u]=disc[u]=++tim;
  38.     int child=0;
  39.     L(i,0,SZ(adj[u])){
  40.         int v=adj[u][i];
  41.         if(!vis[v]){
  42.             child++;
  43.             parent[v]=u;
  44.             dfs(v);
  45.             low[u]=min(low[v],low[u]);
  46.             if(parent[u]!=-1 && low[v]>=disc[v])
  47.                 AP[u]=1;
  48.             if(parent[u]==-1 && child > 1)
  49.                 AP[u]=1;
  50.  
  51.                 /** in case of bridges if(low[u] > disc[v]) add edge u,v**/
  52.         }
  53.         else if(v!=parent[u]){low[u]=min(low[u],disc[v]);}/****/
  54.     }
  55.  
  56. }
  57.  
  58. int main(){
  59. //    WF("out.txt");
  60.     int n;
  61.     while(in(n)){
  62.         if(!n)return 0;init();
  63.         string s;
  64.         getline(cin, s);
  65.         while(1){
  66.             getline(cin, s);
  67.             if(s=="0")break;
  68.             string temp;vi a;
  69.             L(i,0,SZ(s)){
  70.                 if(s[i]==' '){
  71.                     int x;
  72.                     stringstream ss; ss << temp; ss >> x; a.pb(x);
  73.                     temp.clear();
  74.                 }
  75.                 else{
  76.                     temp+=s[i];
  77.                 }
  78.             }
  79.             if(SZ(temp)){
  80.                 int x;
  81.             stringstream ss; ss << temp; ss >> x; a.pb(x);
  82.             }
  83.  
  84.             L(i, 1, SZ(a))
  85.                 adj[a[0]].pb(a[i]), adj[a[i]].pb(a[0]);
  86.         }
  87.         L(i,1,n+1){ if(!vis[i]) dfs(i);}
  88.         int ans=0;
  89.         L(i,1,n+1)if(AP[i])ans++;
  90.         cout << ans <<endl;
  91.         }
  92.  
  93. }
Advertisement
Add Comment
Please, Sign In to add comment