Monday, July 11, 2011

UVa 315 - Network

Problem Link:

Problem in short -
Given an undirected graph with N nodes, we'll need to find no. of articulation points in that graph.
 I've used the Tarjan's algorithm described in Wikipedia ( There's also an algorithm described here - , but this one is probably overly complicated with many variables.

For a non-root node to be a non-articulation point, at least one of the nodes lower than that node in the depth first tree need to have a back edge to any node upper in the tree. So, we'll keep track of each node's level (or depth) with root's depth being 0. We'll also define a variable low for each node. low is the lowest depth of neighbours of all descendants of a particular node in the depth-first tree. A node x will be articulation point, if one of its child y has a low value that is greater than or equal depth of node x.

For a root node to be an articulation point, it has to have more than one child.

C++ source code follows -
#pragma warning(disable:4786)
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <vector>
using namespace std;

#define rep(i,n) for(i=0;i<(n);i++)
#define min(a,b) (((a)<(b))?(a):(b))
#define MAXN 105

int n;
char s[5000];

struct Node {
 int level;
 int low;
 int noChildren;
 vector<int> adj;

int res;
bool isArtic[MAXN];

vector<string> parse(const string& s,const string& delim=" ") {
 string t;
 for(int i=0;i!=s.size();i++) {
  if(delim.find(s[i]) != string::npos) {
   if(!t.empty()) {
  else t+=s[i];
 if(!t.empty()) res.push_back(t);
 return res;

void dfs(int x) {
 nd[x].low = nd[x].level;

 int i, y;
 rep(i, nd[x].adj.size()) {
  y = nd[x].adj[i];
  if( nd[y].level == -1) { //unvisited
   nd[y].level = nd[x].level + 1;
   nd[x].low = min(nd[x].low, nd[y].low);

   if(nd[x].level > 0 && nd[y].low >= nd[x].level) { // x is a non-root node and there's no way from y to any upper level of x
    isArtic[x] = 1;
  else if (nd[y].level < nd[x].level - 1) { //y's depth is lower than x's its a back edge
   nd[x].low = min(nd[x].low, nd[y].level);

 if(nd[x].level == 0) { //root node
  if(nd[x].noChildren >= 2) isArtic[x] = 1;

int main() {
 vector<string> vs;
 int i;
 int u,v;
 while(scanf(" %d",&n)==1) {
  if(n == 0) break;
  gets(s); //garbage
  rep(i,n) nd[i].adj.clear(), nd[i].noChildren = 0,  nd[i].low = nd[i].level = -1;
  while(gets(s)) {
   vs = parse(s);
   if(vs.size() == 1 && vs[0] == "0") break;
   u = atoi(vs[0].c_str()) - 1;
   for(i=1;i<vs.size();i++) {
    v = atoi(vs[i].c_str()) - 1;

  memset(isArtic, 0, sizeof(isArtic));
  nd[0].level = 0;
  res = 0;
  rep(i,n) if(isArtic[i]) res++;
 return 0;


  1. nice blog! i also maintain something of this very kind! check out mine @

  2. wow! I didn't notice that you are back in blogging!! ..hope u continue this time for a bit longer.. :)

  3. It's not possible to write daily now. But I'll try to write at least weekly.

  4. i used a similar approach , but getting wrong answer again and again ,
    my code here : ,it will be very helpful if someone can point out the bug