UVa : 10765 :: Doves and Bombs

Problem : Please find the problem here.

Summary and Explanation : The problem asked to find the vertices with the maximum number of childrens. These vertices mostly (not entirely) are the Articulation points. Since we need to print m such vertices, if we run out of Articulation points in the graph then we can just print the ordinary vertices with maximum number of childs.
This problem is so general that I dont want to use the term articulation points, because we just need to print the nodes with maximum number of childrens with their node index in the order asked in the problem.

Code : Used DFS. Stored the number of childrens for each vertex. Notice at the end of DFS, the If condition is for cycles in the graph. In case of a cycle strating from the given node, the number of childrens for that node should be decreased by 1.

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

const int mxN = 1e4;
int n, m, u, v, timer, tin[mxN], low[mxN], c[mxN];
vector<int> adj[mxN];
array<int, 2> ans[mxN]; // index 0 strores the vertex no. | index 1 stores the number of childrens of the vertex;
bool vis[mxN];

bool cmp(array<int, 2> a, array<int, 2> b){
    if(a[1] != b[1]){
        return a[1] > b[1];
    }
    else{
        return a[0] < b[0];
    }
}

void dfs(int u, int pu = -1){
    vis[u] = 1;
    tin[u] = low[u] = timer++;
    int children = 0;
    for(int v : adj[u]){
        if(v == u) continue;
        if(vis[v]){
            low[u] = min(low[u], tin[v]);
        }
        else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= tin[u] && pu != -1){
                ans[u][1]++;
            }
            c[u]++;
            children++;
        }
    }
    if(pu == -1 && children > 1){
        ans[u][1] = children-1;
    } 
}

void init(){
    memset(vis, false, sizeof(vis));
    memset(tin, 0, sizeof(tin));
    memset(low, 0, sizeof(low));
    memset(c, 0, sizeof(c));
    timer = 0;
    for(int i = 0; i < n; i++){
        adj[i].clear();
        ans[i][0] = i;
        ans[i][1] = 0;
    }
}

int main()
{
    ofstream fout("out");
    while(scanf("%d %d", &n, &m) && (n&&m)){
        init();
        while(scanf("%d %d", &u, &v) && !(u == -1 || v == -1)){
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }
        for(int i = 0; i < n; i++){
            if(!vis[i]){
                dfs(i);
            }
        }
        sort(ans, ans+n, cmp);
        for(int i = 0; i < m; i++){
            cout << ans[i][0] << ' ' << ans[i][1]+1 << '\n';

        }
        cout << '\n';
    }
    return 0;
}