HackerRank Zurikela's Graph Problem Solution

In this post, we will solve HackerRank Zurikela’s Graph Problem Solution.

Zurikela is creating a graph with a special graph maker. At the begining, it is empty and has no nodes or edges. He can perform 3 types of operations:

Ax: Create a set of a new nodes and name it set-K.
Bay: Create edges between nodes of set-x and set-y.
Ca: Create a set composed of nodes from set- and its directly and indirectly connected nodes, called set-K. Note that each node can only exist in one set, so other sets become empty.
The first set’s name will be set-1. In first and third operation K is referring to the index of
new set:

K = [index of last created set] + 1

Create the graph by completing the Q operations specified during input. Then calculate the
maximum number of independent nodes (i.e.:how many nodes in the final graph which don’t have direct edge between them).
Input Format
The first line contains Q.
The Q subsequent lines each contain an operation to be performed.

Output Format

Print maximum number of independent nodes in the final graph (i.e.: nodes which have no direct connection to one another).

Sample Input

8
A 1
A 2
B 1 2
C 1
A 2
A 3
B 3 4
B 4 5

Sample Output

HackerRank Zurikela's Graph Problem Solution — HackerRank Zurikela’s Graph Problem Solution

Zurikela’s Graph C Solution

#include <stdio.h>
#include <stdlib.h>
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
void insert_edge(int x,int y,int w);
void dfs(int x,int y);
int max(int x,int y);
char str[2];
int a[100000],dp1[2][100000],track[100000]={0};
lnode *table[100000]={0};

int main(){
  int Q,x,y,c=0;
  scanf("%d",&Q);
  while(Q--){
    scanf("%s",str);
    switch(str[0]){
      case 'A':
        scanf("%d",&x);
        a[c++]=x;
        break;
      case 'B':
        scanf("%d%d",&x,&y);
        insert_edge(x-1,y-1,1);
        break;
      default:
        scanf("%d",&x);
        dfs(x-1,-1);
        a[c++]=max(dp1[0][x-1],dp1[1][x-1]);
    }
  }
  for(x=y=0;x<c;x++)
    if(!track[x]){
      dfs(x,-1);
      y+=max(dp1[0][x],dp1[1][x]);
    }
  printf("%d",y);
  return 0;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=w;
  t->next=table[y];
  table[y]=t;
  return;
}
void dfs(int x,int y){
  lnode *p;
  track[x]=1;
  for(p=table[x];p;p=p->next)
    if(p->x!=y)
      dfs(p->x,x);
  dp1[1][x]=0;
  dp1[0][x]=a[x];
  for(p=table[x];p;p=p->next)
    if(p->x!=y){
      dp1[0][x]+=dp1[1][p->x];
      if(dp1[0][p->x]>dp1[1][p->x])
        dp1[1][x]+=dp1[0][p->x];
      else
        dp1[1][x]+=dp1[1][p->x];
    }
  return;
}
int max(int x,int y){
  return (x>y)?x:y;
}

Zurikela’s Graph C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

const int NUMS = 100001;
int V[NUMS];
std::vector<int> adj[NUMS];
int dir[NUMS][2];
bool g_b[NUMS];


void recursive_check(int a, int b)
{
    g_b[a] = true;
    dir[a][0] = 0;
    dir[a][1] = V[a];
    
    for (auto& v: adj[a])
    {
        if(v != b)
        {
            recursive_check(v, a);
            dir[a][0]+=max(dir[v][0], dir[v][1]);
            dir[a][1]+=dir[v][0];
        }
    }                
}

int main()
{
    //ofstream fout(getenv("OUTPUT_PATH"));

    string t_temp;
    getline(cin, t_temp);

    int Q = stoi(ltrim(rtrim(t_temp)));

    int t = 1;    
    for (int t_itr = 0; t_itr < Q; t_itr++)
    {
        string first_multiple_input_temp;
        getline(cin, first_multiple_input_temp);

        vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));
        char O = first_multiple_input[0][0];
        
        switch (O)
        {
            case 'A' :
            {
                int a = stoi(ltrim(rtrim(first_multiple_input[1])));
                V[t++] = a;
            }
                break;
                
            case 'B' :
            {
                int a = stoi(ltrim(rtrim(first_multiple_input[1])));
                int b = stoi(ltrim(rtrim(first_multiple_input[2])));
                adj[a].push_back(b);
                adj[b].push_back(a);
            }
                break;

            case 'C' :
            {
                int a = stoi(ltrim(rtrim(first_multiple_input[1])));
                recursive_check(a, a);
                V[t++] = std::max(dir[a][0], dir[a][1]);
            }
                break;
                
        }
    }


    int result = 0;
    for (int i = 1; i <= t; ++i)
    {
        if (!g_b[i])
        {
            recursive_check(i, i);
            result += std::max(dir[i][0], dir[i][1]);
        }
    }
    cout << result << "\n";
    //fout.close();

    return 0;
}




string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}

Zurikela’s Graph C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        var zg = new ZGraph();
        
        int q = int.Parse(Console.ReadLine());
        for (int i = 0; i < q; i++) {
            var sarr = Console.ReadLine().Split(' ');
            switch (sarr[0]) {
                case "A": zg.A(int.Parse(sarr[1])); break;
                case "B": zg.B(int.Parse(sarr[1])-1, int.Parse(sarr[2])-1); break;
                case "C": zg.C(int.Parse(sarr[1])-1); break;
            }
        }
        Console.WriteLine(zg.FinalIndependentCount());
    }
}

class ZGraph {
    List<ZNode> sets = new List<ZNode>(); // disjoint set of nodes
    
    class ZNode {
        public int independents;
        public ZNode parent;
        public List<ZNode> children;
        public int solvedChildren;
        
        public ZNode (int x) {
            independents = x;
            parent = null;
            children = null;
            solvedChildren = 0;
        }
        
        public void AddChild(ZNode y) {
            if (children == null)
                children = new List<ZNode>();
            children.Add(y);
        }
        
        public bool ChildrenSolved {
            get {
                if (children == null)
                    return true;
                return solvedChildren == children.Count;
            }
        }
        
        public void Kill() {
            independents = 0;
            parent = null;
            children = null;
            solvedChildren = 0;
        }
    }
    
    public void A (int x) {
       // Create a set with x nodes
       sets.Add(new ZNode(x));
    }   
    
    public void B (int x, int y) {
        // Create edges between nodes of set x and nodes of set y
        sets[y].parent = sets[x];
        sets[x].AddChild(sets[y]);        
    }
    
    public void C (int x) {
        // Merge x and its connected nodes into set x
        
        // This requires solving maximum-weight independent set problem for a tree,
        // which can be done using DP
        var root = sets[x];
        while (root.parent != null)
            root = root.parent;

        
        if (root.children == null) {
            // trivial tree
            A(root.independents);
            sets[x] = null;
            return;
        }
        
        // set x = root
        
        var tree = new List<ZNode>();
        
        var q = new Queue<ZNode>();
        var dpq = new Queue<ZNode>();
        q.Enqueue(root);
        while (q.Count > 0) { // Use q to fill tree
            var node = q.Dequeue();
            tree.Add(node);
            if (node.children == null) {
                // node is leaf
                node.parent.solvedChildren++;
                if (node.parent.ChildrenSolved)
                    dpq.Enqueue(node.parent);
            } else {
                foreach (var child in node.children)
                    q.Enqueue(child);
            }
        }
        
        
        while (dpq.Count > 0) { // Now use dpq to do dp
            var node = dpq.Dequeue();
            // Either node is in (and we get all grandchildren) or node is not in (and we get all children)
            
            int nodeActiveScore = node.independents;
            if (node.children != null)
                foreach (var child in node.children)
                    if (child.children != null)
                        foreach (var grandchild in child.children)
                            nodeActiveScore += grandchild.independents;
            
            int nodeInactiveScore = 0;
            if (node.children != null)
                foreach (var child in node.children)
                    nodeInactiveScore += child.independents;
            
            node.independents = Math.Max(nodeActiveScore, nodeInactiveScore);
            if (node.parent != null) {
                node.parent.solvedChildren++;
                if (node.parent.ChildrenSolved)
                    dpq.Enqueue(node.parent);
            }
        }
        A(root.independents);
        
        q.Enqueue(root);
        while (q.Count > 0) { // now use q to kill nodes
            var node = q.Dequeue();
            if (node.children != null)
                foreach (var child in node.children)
                    q.Enqueue(child);
            node.Kill();
        }
    }
    
    public int FinalIndependentCount () {
        // This function must be called last as it Cs all roots
        int totalIndependents = 0;
        for (int i = 0; i < sets.Count; i++) {
            if (sets[i].parent == null && sets[i].children != null) {
                C(i);
            } else {
                totalIndependents += sets[i].independents;
            }
        }
        
        return totalIndependents;
    }
}

Zurikela’s Graph Java Solution

import java.io.*;
import java.util.*;

public class Solution {

    static HashMap<Integer,HashSet<Integer>> edges =new HashMap<Integer,HashSet<Integer>>();
    static HashMap<Integer,Integer> directed = new HashMap<Integer,Integer>();
    static HashMap<Integer,Integer> values = new HashMap<Integer,Integer>();
    static HashMap<Integer,int[]> dp;
    public static void main(String[] args) throws Exception{
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int Q = Integer.parseInt(br.readLine());
        HashSet<Integer> sets = new HashSet<Integer>();
        edges =new HashMap<Integer,HashSet<Integer>>();
        directed = new HashMap<Integer,Integer>();
        values = new HashMap<Integer,Integer>();
        int K = 1;
        for(int i = 0; i < Q; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String op = st.nextToken();
            if(op.equals("A")){
                int x = Integer.parseInt(st.nextToken());
                values.put(K, x);
                edges.put(K, new HashSet<Integer>());
                sets.add(K);
                K++;
            }
            else if(op.equals("B")){
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                directed.put(y,x);
                edges.get(x).add(y);
                edges.get(y).add(x);
            }
            else{
                dp = new HashMap<Integer,int[]>();
                int x = Integer.parseInt(st.nextToken());
                int min = x;
                HashSet<Integer> used = new HashSet<Integer>();
                Queue<Integer> stuff = new LinkedList<Integer>();
                stuff.add(x);
                used.add(x);
                sets.remove(x);
                while(stuff.size() > 0){
                    int curr = stuff.remove();
                    for(int adj: edges.get(curr)){
                        if(!used.contains(adj)){
                            min = Math.min(min,adj);
                            stuff.add(adj);
                            used.add(adj);
                            sets.remove(adj);
                        }
                    }
                }
                recur(min);
                values.put(K, dp.get(min)[0]);
                edges.put(K, new HashSet<Integer>());
                sets.add(K);
                K++;
            }
        }
        int finalans = 0;
        while(sets.size() > 0){
            int x = 0;
            for(int i: sets){
                x = i;
                break;
            }
            int min = x;
            HashSet<Integer> used = new HashSet<Integer>();
            Queue<Integer> stuff = new LinkedList<Integer>();
            stuff.add(x);
            used.add(x);
            sets.remove(x);
            while(stuff.size() > 0){
                int curr = stuff.remove();
                for(int adj: edges.get(curr)){
                    if(!used.contains(adj)){
                        min = Math.min(min,adj);
                        stuff.add(adj);
                        used.add(adj);
                        sets.remove(adj);
                    }
                }
            }
            recur(min);
            finalans += dp.get(min)[0];
        }
        System.out.println(finalans);
    }

    static void recur(int root){
        int[] temp = new int[2];
        for(int child: edges.get(root)){
            if(directed.keySet().contains(child) && root == directed.get(child)){
                if(!dp.keySet().contains(child))
                    recur(child);
                temp[1] += dp.get(child)[0];
                temp[0] += dp.get(child)[1];
            }
        }
        temp[0] += values.get(root);
        temp[0] = Math.max(temp[0],temp[1]);
        dp.put(root,temp);
    }
}

Zurikela’s Graph JavaScript Solution

function processData(input) {
    //Enter your code here
  let array = input.split('\n').slice(1);

  let num = array.length;

  let neighbors = {}
  let weights = []
  
  
  const flood_fill = (x, vis) =>{
    vis.add(+x);
    
    neighbors[x].forEach( y => { 
       if(!vis.has(+y)){
        flood_fill(+y,vis)
      }    
    })

   return vis;
  };
    
  const compute_indep = (graph, curr, n) => {
    graph = [...graph] 

    if(n === graph.length){ 
      return curr.map(x => weights[x]).reduce((a,b) => a+b, 0)
    }    
    else if(weights[graph[n]] === 0){     
      return compute_indep(graph, curr, n + 1)
    }

    let ans = compute_indep(graph, curr, n + 1)
    x = graph[n]; 
    let possible = true;

    for(let i = 0; i < curr.length; i++){ 
      if(neighbors[x].has(curr[i])){     
            possible = false;
            break;
         }
    }
    if(possible){  
      ans = Math.max( ans, compute_indep(graph, [...curr , x], n + 1) );  
    }

   return ans
  };      
  
  for(let i = 0; i < num; i++){  
    let current = array[i].split(" ");   
    
    if(current[0] === "A"){
        weights.push(+current[1])
        neighbors[weights.length - 1] = new Set()
    }
    
    else if(current[0] === "B"){
       let a = +current[1]
       let b = +current[2]
       neighbors[a-1].add(b-1);    
       neighbors[b-1].add(a-1);
    }

    else{   
      component = flood_fill(current[1]-1, new Set());
     
      weights.push(compute_indep(component, [], 0));
    
      neighbors[weights.length -1] = new Set();   
     
      component.forEach( x => {
        weights[x] = 0;
        neighbors[x] = new Set();
      });  
    }    
  }
    
  let counted = new Set();
  let ans = 0;
  
  for(let i = 0; i < weights.length; i++){
    if(weights[i] > 0 && !counted.has(i)){
      let component = flood_fill(i, new Set());
      component.forEach( x => {
         counted.add(x);  
      })  

      ans += compute_indep(component, [], 0);
    }   
  };

  console.log(ans)
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
    processData(_input);
});

Zurikela’s Graph Python Solution

# Enter your code here. Read input from STDIN. Print output to STDOUT
Q = int(input().strip())
neighbors = {}
weights = []

def flood_fill(x, vis):
    vis.add(x)
    for y in neighbors[x]:
        if not y in vis:
            flood_fill(y, vis)
    return vis
    
def compute_indep(graph, curr, n):
    if n == len(graph):
        return sum(map(lambda x: weights[x], curr))
    elif weights[graph[n]] == 0:
        return compute_indep(graph, curr, n + 1) 
    ans = compute_indep(graph, curr, n + 1)  
    x = graph[n]
    possible = True
    for y in curr:
        if y in neighbors[x]:
            possible = False
            break
    if possible:
        ans = max(ans, compute_indep(graph, curr + [x], n + 1))
    return ans

for i in range(Q):
    query = input().strip()
    if query[0] == 'A':
        weights.append(int(query[1:]))
        neighbors[len(weights) - 1] = set()
    elif query[0] == 'B':
        x, y = map(int, query[1:].split())
        neighbors[x-1].add(y-1)
        neighbors[y-1].add(x-1)
    else: # 'C'
        component = list(flood_fill(int(query[1:]) - 1, set()))
        weights.append(compute_indep(component, [], 0))
        neighbors[len(weights) - 1] = set()
        for x in component:
            weights[x] = 0
            neighbors[x] = set()           
counted = set()
ans = 0
for i in range(len(weights)):
    if weights[i] > 0 and i not in counted:
        component = list(flood_fill(i, set()))
        for x in component:
            counted.add(x)
        ans += compute_indep(component, [], 0)
print(ans)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python