Programming Geek
Rated 4.1/5 based on 446 reviews

Code Gladiators 2015 Solution : Medium Level



Problem Statement
Problem

As a commander of an army battalion, you have to plan the attack on some enemy cities which are connected by road-network. Before starting the attack, you have information about all the cities and roads connecting them. You can start attack from any city but you must travel from one city to another via roads only. To prevent enemy re-enforcement and block transport through a city, you reach there, destroy it and burn it while leaving behind. This makes it impossible for you to return to a city (via any road) destroyed by you in past. Given a list of all the roads (each connecting a pair of cities), you have to tell what is the maximum number of cities that can be destroyed by the strategy mentioned above. (you can assume that number of cities is 0<=number of cities<=1000 )


Input/Output Specifications
Input Specification

Input Specification

List of all the roads{ list of pairs x#y which denotes that there exists a direct road from city ‘x’ to city ‘y’ }
Output Specification

Output Specification

The maximum number of cities that can be destroyed
Example
Example

Input    : {1#2,2#3,1#11,3#11,4#11,4#5,5#6,5#7,6#7,4#12,8#12,9#12,8#10,9#10,8#9}
Output : 9

Solution
Solution

Algorithm

1) Create Adjacency List for each edge, Remember the Graph is bidirected.
2) Let maximum no of city, max=0. 
3. for each vertex u, 
     i) Topologically Sort all vertices using vertex u as source vertex. 
     ii)for every vertex v, distacne[v]=-999999. 
     iii)for every vertex v adjacent to u 
         ii.a) if(distance[v]< distacne[u]+weight[u][v]) 
                    distance[v]=distance[u]+weight[u][v]; 
     iii)max=maximum(max,distance) 
4. return max.

JavaScript Solution


  var visited = [];
  var Graph = {};
  var Vertex = function(name, weight) {
    this.name = name;
    this.weight = weight;
  };
  var stack = [];
  var addEdge=function(source,destination,weight){
    if (Graph[source]) {
      Graph[source].push(new Vertex(destination, weight));
    } else {
      Graph[source] = [];
      Graph[source].push(new Vertex(destination, weight));
    }
  };

  var Dfs = function(Graph, source) {
    visited[source] = true;
    if (Graph[source])
      for (var index in Graph[source]) {
        if (!visited[Graph[source][index]['name']]) {
          Dfs(Graph, Graph[source][index]['name']);
        }
      }
    stack.push(source);
  };
  var longestPath = function(source) {
    var distance = {};
    var n = 0;
    for (var item in Graph) {
      distance[item] = -9999;
      n++;
    }
    distance[source] = 0;
    while (stack.length) {
      var u = stack.pop();
      if (distance[u] != -9999 && Graph[u]) {
        for (var i in Graph[u]) {
          if ((distance[Graph[u][i]['name']]) < (distance[u] + Graph[u][i]['weight'])) {
            distance[Graph[u][i]['name']] = (distance[u] + Graph[u][i]['weight']);
          }
        }
      }
    }
    var max = -9999;
    for (var index in distance) {
      if (distance[index] > max)
        max = distance[index];
    }
    return max;

  };
  function maxno_city(input1)
   {
    for (var item in input1) {
      var vertices = input1[item].split("#");
        addEdge(vertices[0],vertices[1],1);
        addEdge(vertices[1],vertices[0],1);
    }
    var max=0;
    for(var i in Graph){
      visited=[];
      stack=[];
      Dfs(Graph,i);
      max=Math.max(max,longestPath(i));
    }
    return max;
   }
            
All 10 test cases passed.