Table of Contents
Zurikela’s Graph – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
vector<int> weight;
vector<vi> tree;
vector<int> child;
vector<int> memo;
int K;
int recTree(int i, int p, int j, bool b) {
if(tree[i].size() == j) {
int &r = memo[(K + i) * 2 + b];
if(r != -1) return r;
if(!b) {
return r = 0;
} else if(child[i] == -1) {
return r = weight[i];
} else {
r = 0;
rep(cb, 2)
amax(r, recTree(child[i], -1, 0, cb != 0));
return r;
}
}
int c = tree[i][j];
if(c == p)
return recTree(i, p, j + 1, b);
int &r = memo[c * 2 + b];
if(r != -1) return r;
r = 0;
amax(r, recTree(c, i, 0, false) + recTree(i, p, j + 1, b));
if(!b)
amax(r, recTree(c, i, 0, true) + recTree(i, p, j + 1, b));
return r;
}
void traverse(int x, vi &q, vector<bool> &vis) {
q.clear();
q.push_back(x);
for(int h = 0; h != q.size(); ++ h) {
int i = q[h];
for(int j : tree[i]) if(!vis[j]) {
vis[j] = true;
q.push_back(j);
}
}
}
int main() {
int Q;
while(~scanf("%d", &Q)) {
K = 0;
weight.assign(Q, -1);
tree.assign(Q, vi());
child.assign(Q, -1);
vi q;
vector<bool> vis(Q, false);
for(int ii = 0; ii < Q; ++ ii) {
char ty[10];
scanf("%s", ty);
if(*ty == 'A') {
int x;
scanf("%d", &x);
weight[K] = x;
++ K;
} else if(*ty == 'B') {
int x; int y;
scanf("%d%d", &x, &y), -- x, -- y;
if(!vis[x] && !vis[y]) {
tree[x].push_back(y);
tree[y].push_back(x);
}
} else if(*ty == 'C') {
int x;
scanf("%d", &x), -- x;
traverse(x, q, vis);
child[K] = x;
++ K;
} else abort();
}
memo.assign(K * 4, -1);
int ans = 0;
rep(i, K) if(!vis[i]) {
traverse(i, q, vis);
int x = 0;
rep(b, 2)
amax(x, recTree(i, -1, 0, b != 0));
ans += x;
}
printf("%d\n", ans);
}
return 0;
}
Java rep HackerRank Solution
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
/**
* Created by hama_du on 2016/01/30.
*/
public class Solution {
static int MAX = 100010;
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
graph = new List[MAX];
for (int i = 0; i < MAX ; i++) {
graph[i] = new ArrayList<>();
}
int q = in.nextInt();
value = new int[MAX];
touched = new boolean[MAX];
int k = 0;
while (--q >= 0) {
char c = in.nextChar();
if (c == 'A') {
int num = in.nextInt();
value[k] = num;
k++;
} else if (c == 'B') {
int a = in.nextInt()-1;
int b = in.nextInt()-1;
graph[a].add(b);
graph[b].add(a);
} else {
int root = in.nextInt()-1;
int[] num = dfs(root, -1);
value[k] = Math.max(num[0], num[1]);
k++;
}
}
Arrays.fill(touched, false);
int sum = 0;
for (int i = 0 ; i < MAX ; i++) {
if (!touched[i]) {
int[] res = dfs(i, -1);
sum += Math.max(res[0], res[1]);
}
}
out.println(sum);
out.flush();
}
static boolean[] touched = new boolean[MAX];
static int[] value;
static List<Integer>[] graph;
static int[] dfs(int now, int par) {
touched[now] = true;
int take = value[now];
int nontake = 0;
for (int to : graph[now]) {
if (to == par) {
continue;
}
int[] res = dfs(to, now);
take += res[1];
nontake += Math.max(res[0], res[1]);
}
graph[now].clear();
value[now] = 0;
return new int[]{take, nontake};
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
private int next() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public char nextChar() {
int c = next();
while (isSpaceChar(c))
c = next();
if ('a' <= c && c <= 'z') {
return (char) c;
}
if ('A' <= c && c <= 'Z') {
return (char) c;
}
throw new InputMismatchException();
}
public String nextToken() {
int c = next();
while (isSpaceChar(c))
c = next();
StringBuilder res = new StringBuilder();
do {
res.append((char) c);
c = next();
} while (!isSpaceChar(c));
return res.toString();
}
public int nextInt() {
int c = next();
while (isSpaceChar(c))
c = next();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = next();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c-'0';
c = next();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = next();
while (isSpaceChar(c))
c = next();
long sgn = 1;
if (c == '-') {
sgn = -1;
c = next();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c-'0';
c = next();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
static void debug(Object... o) {
System.err.println(Arrays.deepToString(o));
}
}
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
Q = int(raw_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 xrange(Q):
query = raw_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 xrange(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
Python 3 rep HackerRank Solution
from collections import deque
class IndepSet:
def __init__(self, seed):
self.value = self.bestfor(0,{seed},set())
# print("Indep set: value", self.value)
def bestfor(self,value,fringe,visited):
# if self.best and self.best:
# pass
if not fringe:
self.visited = visited
return value
v = fringe.pop()
adj = {a for a in v.adjacent if a not in visited}
incl_vis = visited.union({v}, adj)
incl = self.bestfor(value + v.value, fringe.union(adj, *[a.adjacent for a in adj]).difference(incl_vis), incl_vis)
excl = self.bestfor(value, fringe.union(adj), visited.union({v}))
return max(incl, excl)
class MetaNode:
def __init__(self, value, id):
self.value = value
self.adjacent = set()
self.id = id
def __repr__(self):
return "<%d: value %d%s>" % (self.id, self.value, " LINKED: " + ",".join([str(a.id) for a in self.adjacent]) if self.adjacent else "")
class Main:
def __init__(self):
self.v = [None]
ops = int(input())
for i in range(ops):
self.readcommand()
# print(self.indep(), self.v)
print(self.indep())
def readcommand(self):
cmd, *params = input().split()
# print(cmd, params)
if cmd == 'A':
num = int(params[0])
node = MetaNode(num, len(self.v))
self.v.append(node)
elif cmd == 'B':
xi,yi = map(int, params)
self.v[xi].adjacent.add(self.v[yi])
self.v[yi].adjacent.add(self.v[xi])
elif cmd == 'C':
xi = int(params[0])
i = IndepSet(self.v[xi])
for n in i.visited:
# print("Clearing", n.id)
self.v[n.id] = None
new = MetaNode(i.value, len(self.v))
self.v.append(new)
def indep(self):
visited = set()
value = 0
for i in range(len(self.v)):
if self.v[i]:
if self.v[i] in visited:
continue
if self.v[i].adjacent:
s = IndepSet(self.v[i])
visited = visited.union(s.visited)
# print("%d: Adding %d (linked)" % (i, s.value))
value += s.value
else:
# print("%d: Adding %d (solo)" % (i, self.v[i].value))
value += self.v[i].value
return value
Main()
C rep HackerRank Solution
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
