runtah

#Articulation Points #Graph #DFS #BFS
Method:
Turn off each node and see if all the other nodes except that are visited or not using DFS
Sample I/O:

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
5
1 2
2 3 4
4 5
0
0

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool con[200][200];
vector< pair<int, int> > edges;
bool visit[200];

void init_con(int n) {
 for (int i=0 ; i<=n ; i++)
 for (int j=0 ; j<=n ; j++)
 con[i][j] = false;
}

int dfs_visit(int s, int n) {

 int vCount = 1;

 if (visit[s]) return 0;
 visit[s] = true;

 for (int i=1 ; i<=n ; i++) {
 if (!visit[i] && con[s][i]) {
 vCount += (dfs_visit(i,n));
 }
 }
 return vCount;
}

int dfs(int s, int n) {

 int vCount = 0;

 for (int i=1 ; i<=n ; i++) {
 visit[i] = false;
 }
 visit[s] = true;

 for (int i=1 ; i<=n ; i++) {
 if (!visit[i]) {
 vCount = dfs_visit(i,n);

 return vCount;
 }
 }
 return vCount;
}

int find_bridges(int n) {
 int aps = 0, i, j;


 for (int i=1 ; i<=n ; i++) {
 if (dfs(i,n) != (n-1)) aps++;
 }


 return aps;
}
char buf[10000];
int main( void ) {


 //freopen("inp.dat","r+",stdin);

 int n, result, vtx, plc;
 char *p;

 while (scanf("%d",&n)==1 && n!=0) {
 getchar();

 init_con(n);
 edges.clear();

 while (gets(buf)) {
 if (!strcmp(buf,"0")) break;
 p = strtok(buf," ");
 sscanf(p,"%d",&plc);

 while ((p=strtok(NULL," "))) {
 sscanf(p,"%d",&vtx);

 con[plc][vtx] = con[vtx][plc] = true;
 edges.push_back(make_pair(plc,vtx));
 }
 }

 result = find_bridges(n);

 cout << result << endl;
 }


 return 0;
}