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] + 1Create 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
5
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)
