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