Hackerrank - Even Tree - Pavol Pidanič

Problem Statement
A description of the problem can be found on Hackerrank.

Solution
Make a map of a node vs. the nnumber of nodes connected to it. Iterate over the map. If for the i^th node, the number of nodes connected is even, then iterate over the nodes list connected to this node. Now for every connected j^th node, again get the number of nodes connected this j^th node. If the number of nodes connected to j^th node is odd, cut the edge.

I created solution in:

Java
JavaScript
Scala
Ruby

All solutions are also available on my GitHub.

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class EvenTree
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int vertices = scanner.nextInt();
        int edges = scanner.nextInt();
        int[] tree = new int[vertices + 1];

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < edges; i++)
        {
            int connected = scanner.nextInt();
            int parent = scanner.nextInt();
            tree[connected] = parent;

            if(map.get(parent) == null)
            {
                map.put(parent, 1);
            }
            if(map.get(connected) == null)
            {
                map.put(connected, 1);
            }

            int count = map.get(parent);
            map.put(parent, ++count);
        }

        int result = 0;
        for (int nodeIndex = tree.length - 1; nodeIndex > 1; nodeIndex--)
        {
            if(map.get(nodeIndex) % 2 == 0)
            {
                boolean hasEven = false;
                for (int i = tree.length - 1; i > 1; i--)
                {
                    if(tree[i] == nodeIndex)
                    {
                        int node = i;
                        // System.out.println(node);
                        if(map.get(node) % 2 == 0)
                        {
                            hasEven = true;
                        }
                    }
                }
                if(!hasEven)
                {
                    result++;
                    // System.out.println("cut " +nodeIndex);
                    int parent = tree[nodeIndex];
                    tree[nodeIndex] = 0;
                    // System.out.println("parent " + parent);
                    int count = map.get(parent);
                    map.put(parent, --count);
                }
                // System.out.println();
            }
        }
        System.out.println(result);
        scanner.close();
    }
}

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

public class EvenTree

{

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

int vertices = scanner.nextInt();

int edges = scanner.nextInt();

int[] tree = new int[vertices + 1];

Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < edges; i++)

{

int connected = scanner.nextInt();

int parent = scanner.nextInt();

tree[connected] = parent;

if(map.get(parent) == null)

{

map.put(parent, 1);

}

if(map.get(connected) == null)

{

map.put(connected, 1);

}

int count = map.get(parent);

map.put(parent, ++count);

}

int result = 0;

for (int nodeIndex = tree.length - 1; nodeIndex > 1; nodeIndex--)

{

if(map.get(nodeIndex) % 2 == 0)

{

boolean hasEven = false;

for (int i = tree.length - 1; i > 1; i--)

{

if(tree[i] == nodeIndex)

{

int node = i;

// System.out.println(node);

if(map.get(node) % 2 == 0)

{

hasEven = true;

}

if(!hasEven)

{

result++;

// System.out.println("cut " +nodeIndex);

int parent = tree[nodeIndex];

tree[nodeIndex] = 0;

// System.out.println("parent " + parent);

int count = map.get(parent);

map.put(parent, --count);

}

// System.out.println();

}

System.out.println(result);

scanner.close();

}

JavaScript

'use strict';

const processData = input => {
    let lines = input.split('\n');
    let counts = lines[0].split(" ").map(i => parseInt(i));
    let vertices = counts[0];
    let edges = counts[1];
    let edgesDesc = lines.slice(1);

    let tree = new Array(vertices + 1, 0);
    let map = {};

    for(let i = 0; i < edges; i++) {
        let splits = edgesDesc[i].split(' ').map(i => parseInt(i));
        let connected = splits[0];
        let parent = splits[1];
        tree[connected] = parent;

        if(!map[parent]){
            map[parent] = 1;
        }
        if(!map[connected]) {
            map[connected] = 1;
        }

        let count = map[parent];
        map[parent] = ++count;
    }

    let result = 0;
    for(let nodeIndex = tree.length - 1; nodeIndex > 1; nodeIndex--) {
        if(map[nodeIndex] % 2 === 0) {
            let hasEven = false;
            for(let i = tree.length - 1; i > 1; i--) {
                if(tree[i] == nodeIndex) {
                    let node = i;
                    if(map[node] % 2 == 0) {
                        hasEven = true;
                    }
                }
            }
            if(!hasEven) {
                result++;
                let parent = tree[nodeIndex];
                tree[nodeIndex] = 0;
                let count = map[parent];
                map[parent] = --count;
            }
        }
    }
    console.log(result);
};

process.stdin.resume();
process.stdin.setEncoding("ascii");

var _input = "";
process.stdin.on("data", input => _input += input);
process.stdin.on("end", () => processData(_input));

'use strict';

const processData = input => {

let lines = input.split('\n');

let counts = lines[0].split(" ").map(i => parseInt(i));

let vertices = counts[0];

let edges = counts[1];

let edgesDesc = lines.slice(1);

let tree = new Array(vertices + 1, 0);

let map = {};

for(let i = 0; i < edges; i++) {

let splits = edgesDesc[i].split(' ').map(i => parseInt(i));

let connected = splits[0];

let parent = splits[1];

tree[connected] = parent;

if(!map[parent]){

map[parent] = 1;

}

if(!map[connected]) {

map[connected] = 1;

}

let count = map[parent];

map[parent] = ++count;

}

let result = 0;

for(let nodeIndex = tree.length - 1; nodeIndex > 1; nodeIndex--) {

if(map[nodeIndex] % 2 === 0) {

let hasEven = false;

for(let i = tree.length - 1; i > 1; i--) {

if(tree[i] == nodeIndex) {

let node = i;

if(map[node] % 2 == 0) {

hasEven = true;

}

if(!hasEven) {

result++;

let parent = tree[nodeIndex];

tree[nodeIndex] = 0;

let count = map[parent];

map[parent] = --count;

}

console.log(result);

};

process.stdin.resume();

process.stdin.setEncoding("ascii");

var _input = "";

process.stdin.on("data", input => _input += input);

process.stdin.on("end", () => processData(_input));

Scala

import scala.io.Source
import scala.collection.mutable.Map

object EvenTree extends App {
  val lines = Source.stdin.getLines().toList
  val count = lines.head.split(" ").map(_.toInt)
  val vertices = count(0)
  val edges = count(1)
  val edgesDesc = lines.tail

  val tree = Array.fill(vertices + 1)(0)
  val treeMap: Map[Int, Int] = Map.empty

  edgesDesc.foreach(desc => {
    val nums = desc.split(" ").map(_.toInt)
    val connected = nums(0)
    val parent = nums(1)
    tree(connected) = parent
    if(!treeMap.get(parent).isDefined) {
      treeMap.put(parent, 1)
    }
    if(!treeMap.get(connected).isDefined) {
      treeMap.put(connected, 1)
    }

    val count = treeMap.get(parent).get
    treeMap.put(parent, count + 1)
  })

  var result = 0
  for(nodeIndex <- Range(tree.length - 1, 1, -1)) {
    if(treeMap.get(nodeIndex).get % 2 == 0) {
      var hasEven = false
      for (i <- Range(tree.length - 1, 1, -1)) {
        if(tree(i) == nodeIndex) {
          val node = i
          if(treeMap.get(node).get % 2 == 0) {
            hasEven = true
          }
        }
      }
      if(!hasEven) {
        result += 1
        val parent = tree(nodeIndex)
        tree(nodeIndex) = 0
        val count = treeMap.get(parent).get
        treeMap.put(parent, count - 1)
      }
    }
  }
  println(result)
}

import scala.io.Source

import scala.collection.mutable.Map

object EvenTree extends App {

val lines = Source.stdin.getLines().toList

val count = lines.head.split(" ").map(_.toInt)

val vertices = count(0)

val edges = count(1)

val edgesDesc = lines.tail

val tree = Array.fill(vertices + 1)(0)

val treeMap: Map[Int, Int] = Map.empty

edgesDesc.foreach(desc => {

val nums = desc.split(" ").map(_.toInt)

val connected = nums(0)

val parent = nums(1)

tree(connected) = parent

if(!treeMap.get(parent).isDefined) {

treeMap.put(parent, 1)

}

if(!treeMap.get(connected).isDefined) {

treeMap.put(connected, 1)

}

val count = treeMap.get(parent).get

treeMap.put(parent, count + 1)

})

var result = 0

for(nodeIndex <- Range(tree.length - 1, 1, -1)) {

if(treeMap.get(nodeIndex).get % 2 == 0) {

var hasEven = false

for (i <- Range(tree.length - 1, 1, -1)) {

if(tree(i) == nodeIndex) {

val node = i

if(treeMap.get(node).get % 2 == 0) {

hasEven = true

}

if(!hasEven) {

result += 1

val parent = tree(nodeIndex)

tree(nodeIndex) = 0

val count = treeMap.get(parent).get

treeMap.put(parent, count - 1)

}

println(result)

}

Ruby

(vertices, edges) = gets.split.map{|s| s.to_i}
tree = Array.new(vertices + 1)
map = Hash.new

edges.times do
  (connected, parent) = gets.split.map{|s| s.to_i}
  tree[connected] = parent
  if(!map.has_key?(parent))
    map[parent] = 1
  end
  if(!map.has_key?(connected))
    map[connected] = 1
  end
  count = map[parent]
  map[parent] = count + 1
end

result = 0
puts tree
puts map
(tree.size - 1).downto(1) do |node_index|
  if(map[node_index] % 2 == 0)
    hasEven = false
    (tree.size - 1).downto(1) do |i|
      if(tree[i] == node_index)
        node = i
        if(map[node] % 2 == 0)
          hasEven = true
        end
      end
    end
    if(!hasEven)
      result += 1
      parent = tree[node_index]
      tree[node_index] = 0
      puts parent
      count2 = map[parent]
      map[parent] = count2 - 1
    end
  end
end

puts result

(vertices, edges) = gets.split.map{|s| s.to_i}

tree = Array.new(vertices + 1)

map = Hash.new

edges.times do

(connected, parent) = gets.split.map{|s| s.to_i}

tree[connected] = parent

if(!map.has_key?(parent))

map[parent] = 1

end

if(!map.has_key?(connected))

map[connected] = 1

end

count = map[parent]

map[parent] = count + 1

end

result = 0

puts tree

puts map

(tree.size - 1).downto(1) do |node_index|

if(map[node_index] % 2 == 0)

hasEven = false

(tree.size - 1).downto(1) do |i|

if(tree[i] == node_index)

node = i

if(map[node] % 2 == 0)

hasEven = true

end

if(!hasEven)

result += 1

parent = tree[node_index]

tree[node_index] = 0

puts parent

count2 = map[parent]

map[parent] = count2 - 1

end

puts result

Pavol Pidanič

I can count to 1023 with 10 fingers

Hackerrank – Even Tree