Documentation/docs-sonyckson/315.cpp

   1 /* ARTICULATION POINTS   */
   2 #include <algorithm>
   3 #include <vector>
   4 #include <set>
   5 #include <string>
   6 #include <fstream>
   7 #include <iostream>
   8 #include <iomanip>
   9 #include <map>
  10 #include <sstream>
  11 #include <queue>
  12
  13 #include <cmath>
  14 #include <cstdio>
  15 #include <cctype>
  16 #include <cstdlib>
  17 #include <cstring>
  18
  19 #define forn(i, n) for(int i=0;i<int(n);i++)
  20 #define FOR(i, a, b) for(int i=(a);i<int(b);i++)
  21 #define RFOR(i, b, a) for(int i=(b);i>int(a);i--)
  22 #define foreach(it, c)  for(__typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  23 #define ALL(x)   (x).begin(),(x).end()
  24 #define SIZE(x)   (int)(x).size()
  25 #define SORT(x) sort(ALL(x))
  26 using namespace std;
  27 #define VI vector<int>
  28 #define VS vector<string>
  29 #define PB push_back
  30 #define ISS istringstream
  31 #define OSS ostringstream
  32 typedef long long ll;
  33 // NUNCA DEFINIR int max....
  34 #define M 100000
  35 vector<int> edges[101];
  36 int N;
  37 int id[101], color[101];
  38 int ind =0, res;
  39 int back(int node, int father){
  40         int i,j ,k;
  41         int low = ind;
  42         id[node] = ind++;
  43         color[node] = 1;
  44         int cant = 0;
  45         bool isArt = false;int aux;
  46         for(i=0;i<edges[node].size();i++){
  47                 int v= edges[node][i];
  48                 if( v == father )continue;
  49                 if( color[v] == 0 ){
  50                         cant++, aux = back(v,node);
  51                         if( aux >= id[node] ) isArt = true;
  52                 }else aux = id[v];
  53                 low = min ( low, aux );
  54         }
  55         if( node == 1 )if( cant > 1 )res ++;
  56         else if(isArt )res++;
  57         return low;
  58 }
  59 int main(){
  60         int i, j, k;
  61         bool mat[101][101];
  62         while(1){
  63                 ind=0;
  64                 scanf("%i", &N); if(!N) return 0;
  65                 while(getchar() !='\n' ) ;
  66                 for(i=1;i<=N;i++) edges[i].clear();
  67                 memset(mat, false, sizeof(mat));
  68                 while(1){
  69                         string s;
  70                         getline(cin, s);
  71                         istringstream iss ( s );
  72                         int a, b;
  73                         iss >> a;
  74                         if(!a) break;
  75                         while( iss >> b ){
  76                                 if( !mat[a][b] )
  77                                 edges[b].PB(a), edges[a].PB(b);
  78                                 mat[a][b] = mat[b][a] = true;
  79                         }
  80                 }
  81                 res=0;
  82                 memset(color, 0, sizeof(color));
  83                 back(1,-1);
  84                 printf("%i\n", res);
  85         }return 0;
  86 }