[UVa] 315 - Network

#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;
}