1063 - Ant Hills (LightOJ)

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

vector<int>adj[10007];
//bool visit[100007];
int low[10007],AP[10007],discovery[10007];
int Time=0;

int dfsAP(int src, int parent){
    low[src]=discovery[src]= (++Time);

    int children=0;
    for(int i=0;i<adj[src].size();i++){
        int w=adj[src][i];

        if(w!=parent){ // don't wanna go back to the before node
            if(discovery[w]==0){
                children++;
                dfsAP(w,src);

                if(discovery[src]<=low[w]) AP[src]=1; //Condition 1
                low[src]=min(low[src],low[w]);
            }

            else{
                low[src]=min(low[src],discovery[w]);
            }
        }
    }
    return children;
}


int main()
{
    int t; cin>>t;
    for(int o=1;o<=t;o++){

            memset(low,0,sizeof(low));
            memset(AP,0,sizeof(AP));
            memset(discovery,0,sizeof(discovery));
    Time=0;
        int n,m,res=0;
    cin>>n>>m;

    for(int i=0;i<m;i++) {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }



        AP[1]=dfsAP(1,1)>1; //Condition 2


    for(int i=1;i<=n;i++) if(AP[i]==1) res++;

    cout<<"Case "<<o<<": "<<res<<endl;

    for(int i=0;i<10007;i++) {
        adj[i].clear();
    }
}
return 0;
}