HackerRank Zurikela’s Graph problem solution

In this HackerRank Zurikela’s Graph problem solution, we need to create a graph by completing the Q operations specified during input. then calculate the maximum number of an independent node or how many nodes in the final graph which doesn’t have a direct edge between them.

Problem solution in Python.

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)

Problem solution in Java.

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);
    }
}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

int N;
int A[100001];
vector<int> adj[100001];
bool seen[100001];
int dp[100001][2];

void solve(int u, int p)
{
    seen[u]=true;
    dp[u][0]=0;
    dp[u][1]=A[u];
    for(auto& v: adj[u]) if(v!=p)
    {
        solve(v, u);
        dp[u][0]+=max(dp[v][0], dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}

int main()
{
    scanf("%d", &N);
    char op;
    int a, b;
    int M=1;
    for(int i=0; i<N; i++)
    {
        scanf(" %c", &op);
        if(op=='A')
        {
            scanf("%d", &a);
            A[M++]=a;
        }
        else if(op=='B')
        {
            scanf("%d%d", &a, &b);
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        else if(op=='C')
        {
            scanf("%d", &a);
            solve(a, a);
            A[M++]=max(dp[a][0], dp[a][1]);
        }
    }
    int ans=0;
    for(int i=1; i<=M; i++) if(!seen[i])
    {
        solve(i, i);
        ans+=max(dp[i][0], dp[i][1]);
    }
    printf("%dn", ans);
    return 0;
}

Problem solution in C.

#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;
}