Articulation Point.cpp

/* Articulation Point */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>
using namespace std;
#define MAX 10006

int parent[MAX];
int childCnt[MAX];
int low[MAX];
int dfsTime[MAX];
bool vis[MAX];
bool is_AP[MAX];

vector<int> adj[MAX];

void dfsAP(int u)
{
    static int c = 0;
    vis[u] = true;
    low[u] = dfsTime[u] = c++;
    for(int i=0; i<adj[u].size(); i++){
        int v = adj[u][i];

        if(!vis[v]){
            parent[v] = u;
            childCnt[u]++;
            dfsAP(v);

            low[u] = min(low[u], low[v]);

            if(low[v] >= dfsTime[u]) is_AP[u] = true;
        }
        else {
            if(v != parent[u]){
                low[u] = min(low[u], dfsTime[v]);
            }
        }
    }
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int cases, caseno = 0;
    scanf("%d", &cases);
    while(cases--){
        for(int i=0; i<MAX; i++) adj[i].clear();
        memset(childCnt, 0, sizeof childCnt);
        memset(vis, false, sizeof vis);
        memset(is_AP, false, sizeof is_AP);
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i=1; i<=m; i++){
            int u, v;
            scanf("%d %d", &u, &v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        parent[1] = -1;
        dfsAP(1);

        int cntAP = 0;
        if(childCnt[1] > 1) is_AP[1] = true;
        else is_AP[1] = false;

        for(int i=1; i<=n; i++){
            if(is_AP[i] == true) cntAP++;
        }
        printf("Case %d: %d\n", ++caseno, cntAP);
    }
}