uva 315 - Network

/*

Problem link
Type: Graph, DFS Variant
Algorithm:
 Use the DFS to search for articulation points
 low[u]: the lowest num[v] that u can reach
 num[u]: the order in the DFS when u is visit for the first time
 if low[v]>=num[u], v is a child of u, if v cannot reach any vertex lower than u without
 going through u, this mean when u is remove, v cannot reach any vertex lower than u
 hence u is the articulation point.
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 110;
const int maxe = maxn*maxn;
//-----------------------------------
class Edge { public: int a; int b; };
//-----------------------------------
class EdgeList {
public:
 Edge list[maxe];
 int m;
 int start[maxn],end[maxn];
 
 EdgeList () {
  m = 0;
 }
 
 void sort(int l, int r) {
  int i,j,x;
  Edge tmp;
  i = l; j = r; x = list[(l+r)/2].a;
  do
  {
   while (list[i].a<x) i++;
   while (x<list[j].a) j--;
   if (i<=j)
   {
    tmp = list[i]; list[i] = list[j]; list[j] = tmp;
    i++; j--;
   }
  } while (i<=j);
  if (l<j) sort(l,j);
  if (i<r) sort(i,r);
 }
 
 void init() {
  sort(1,m);
  for (int i=1; i<=m; i++) 
  {
   end[i] = -1;
   start[i] = 0;
  }
  start[list[1].a] = 1;
  for (int i=2; i<=m; i++)
   if (list[i].a!=list[i-1].a)
   {
    start[list[i].a] = i;
    end[list[i-1].a] = i-1;
   }
  end[list[m].a] = m;
 }
 
 void add(int a, int b) {
  m++;
  list[m].a = a;
  list[m].b = b;
 }
};
//-----------------------------------
EdgeList c;
int low[maxn], num[maxn], fa[maxn];
bool fre[maxn], cri[maxn];
int n,nchild,root,cnt;
//-----------------------------------
bool readfile() {
 cin >> n;
 if (n==0) return(false);
 string line;
 getline(cin,line);
 while (true)
 {
  getline(cin,line);
  line = line+" ";
  int u = 0, v = 0, i = 0;
  while (line[i]>='0' && line[i]<='9')
  {
   u = u*10+int(line[i])-48;
   i++;
  }
  if (u==0) break; 
  i++;
  for ( ; i<line.length(); i++)
  {
   if (line[i]==' ') 
   {
    c.add(u,v);
    c.add(v,u);
    v = 0;
   }
   else v = v*10 + int(line[i])-48;
  }
 }
 c.init();
 return(true);
}
//-----------------------------------
void DFS(int u) {
 cnt++;
 low[u] = num[u] = cnt;
 for (int i=c.start[u]; i<=c.end[u]; i++)
 {
  int v = c.list[i].b;
  if (num[v]==0) 
  {
   fa[v] = u;
   if (u==root) nchild++;
   DFS(v);
   if (low[v]>=num[u]) cri[u] = true;
   low[u] = min(low[u],low[v]);
  }
  else if (v!=fa[u]) low[u] = min(low[u],num[v]);
 }
}
//-----------------------------------
int solve() {
 memset(fre,true,sizeof(fre));
 memset(cri,false,sizeof(cri));
 memset(num,0,sizeof(num));
 root = 1;
 nchild = 0;
 cnt = 0;
 DFS(1);
 cri[1] = nchild>1;
 int result = 0;
 for (int i=1; i<=n; i++) 
  if (cri[i]) result++;
 return(result);
}
//-----------------------------------
int main() {
 while (readfile()) 
 {
  cout << solve() << endl;
  c.m = 0;
 }
 return 0;
}
//-----------------------------------