Tree Flow – 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++ Tree Flow HackerRank Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<long long, long long> PII;
long long n,x,y,z,i,ans1,ans2;
vector<PII> edge[500007];
void DFS1(long long bef, long long pos, long long sum) {
long long i;
for (i=0 ; i<edge[pos].size() ; i++) if (edge[pos][i].first != bef) {
DFS1(pos,edge[pos][i].first,sum + edge[pos][i].second);
}
ans1 += sum;
}
void DFS2(long long bef, long long pos, long long sum) {
long long i;
for (i=0 ; i<edge[pos].size() ; i++) if (edge[pos][i].first != bef) {
DFS2(pos,edge[pos][i].first,sum + edge[pos][i].second);
}
ans2 += sum;
}
int main() {
scanf("%lld",&n);
for (i=1 ; i<=n-1 ; i++) {
scanf("%lld%lld%lld",&x,&y,&z);
edge[x].push_back(PII(y,z));
edge[y].push_back(PII(x,z));
}
DFS1(-1,1,0);
DFS2(-1,n,0);
//printf("%lld %lld\n",ans1,ans2);
printf("%lld\n",min(ans1,ans2));
return 0;
}
Java Tree Flow HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
private static InputReader in;
private static PrintWriter out;
static class Edge {
public int to;
public long weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public static void dfs(int node, int par, long cdist) {
dist[node] = cdist;
for (Edge e : graph[node]) {
if (e.to == par) continue;
dfs(e.to, node, cdist+e.weight);
}
}
public static void bfs(int node) {
int front = 0, back = 0;
Arrays.fill(vis, false);
queue[back++] = node;
dist[node] = 0;
vis[node] = true;
while (front < back) {
int cur = queue[front++];
for (Edge e : graph[cur]) {
if (vis[e.to]) continue;
vis[e.to] = true;
dist[e.to] = dist[cur] + e.weight;
queue[back++] = e.to;
}
}
}
public static ArrayList<Edge>[] graph;
public static long[] dist;
public static int[] queue;
public static boolean[] vis;
public static void main(String[] args) throws IOException {
in = new InputReader(System.in);
out = new PrintWriter(System.out, true);
int n = in.nextInt();
graph = new ArrayList[n];
queue = new int[graph.length];
vis = new boolean[graph.length];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int i = 0; i < n-1; i++) {
int a = in.nextInt()-1, b = in.nextInt()-1, c = in.nextInt();
graph[a].add(new Edge(b,c));
graph[b].add(new Edge(a,c));
}
dist = new long[n];
bfs(0);
long ans1 = 0;
for (int i = 0; i < n; i++) ans1 += dist[i];
bfs(n-1);
long ans2 = 0;
for (int i = 0; i < n; i++) ans2 += dist[i];
out.println(Math.min(ans1, ans2));
out.close();
System.exit(0);
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
Python 3 Tree Flow HackerRank Solution
import os
import sys
import heapq
def dfs(graph, start,dlength,EdgeDis):
visited, stack = set(), [start]
distances = [-1] * dlength
distances[int(start) -1]=0
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
for v in graph[vertex]:
if distances[int(v)-1]==-1:
distances[int(v)-1]=distances[int(vertex)-1]+min(EdgeDis[tuple([vertex,v])])
stack.extend(graph[vertex] - visited)
return [x for x in distances if x!=-1]
'''
def bfs(graph, start,dlength,EdgeDis):
visited, queue = set(), [start]
distances = [-1] * dlength
distances[int(start) -1]=0
#print distances
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
#print vertex
for v in graph[vertex]:
#print v,
#if int(v)!=int(start):
if distances[int(v)-1]==-1:
distances[int(v)-1]=distances[int(vertex)-1]+min(EdgeDis[tuple([vertex,v])])
queue.extend(graph[vertex] - visited)
#print distances,'*'*10,visited
return filter(lambda x:x!=-1,distances)
'''
'''
def djikstra(graph,start,n,EdgeDis):
visited,hq=set(),[]
distances=[-1]*n
distances[start-1]=0
heapq.heappush(hq,(distances[int(start) -1],start))
while len(hq)!=0:
(dis,vertex)=heapq.heappop(hq)
if vertex not in visited:
visited.add(vertex)
if distances[vertex-1]==-1:
distances[vertex-1]=dis
for v in graph[vertex]:
if distances[int(v)-1]==-1 or distances[int(v)-1] > dis+min(EdgeDis[tuple([vertex,v])]):
distances[int(v)-1]=dis+min(EdgeDis[tuple([vertex,v])])
heapq.heappush(hq,(distances[int(v)-1],int(v)))
return distances
'''
n=int(eval(input()))
graph=dict()
EdgeDis=dict()
for r in range(n-1):
a,b,c=list(map(int,input().split()))
#make graph and EdgeDistances
graph.setdefault(a,set()).add(b)
graph.setdefault(b,set()).add(a)
EdgeDis.setdefault(tuple([a,b]),list()).append(c)
EdgeDis.setdefault(tuple([b,a]),list()).append(c)
#print graph
#print EdgeDis
sol = dfs(graph,1,n,EdgeDis)
sol2 = dfs(graph,n,n,EdgeDis)
print((min(sum(sol), sum(sol2))))
#print min(sum([0 if k==-1 else int(k) for k in sol]) , sum([0 if k==-1 else int(k) for k in sol2]) )
#sol = ['-1' if k=='inf' else str(k) for k in sol]
#print ' '.join(sol)
Python 2 Tree Flow HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
def dfs(graph, start, n, edge_dist):
visited, stack = set(), [start]
distances = [-1] * n
distances[int(start) -1]=0
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
for v in graph[vertex]:
if distances[int(v)-1]==-1:
distances[int(v)-1]=distances[int(vertex)-1]+min(edge_dist[tuple([vertex,v])])
stack.extend(graph[vertex] - visited)
return filter(lambda x:x!=-1,distances)
n=int(input()) # no. of nodes
graph=dict()
edge_dist=dict()
for r in range(n-1):
# taking input from stdin
a,b,c=map(int, raw_input().split())
# making graph and edge distances
graph.setdefault(a,set()).add(b)
graph.setdefault(b,set()).add(a)
edge_dist.setdefault((a,b),[]).append(c)
edge_dist.setdefault((b,a),[]).append(c)
sol = dfs(graph,1,n,edge_dist)
sol2 = dfs(graph,n,n,edge_dist)
print(min(sum(sol),sum(sol2)))
C Tree Flow HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
void dfs(int x,int y,long long len,long long *ans);
void insert_edge(int x,int y,int w);
lnode *table[500000];
int main(){
int N,x,y,z,i;
long long ans1,ans2;
scanf("%d",&N);
for(i=ans1=ans2=0;i<N-1;i++){
scanf("%d%d%d",&x,&y,&z);
insert_edge(x-1,y-1,z);
}
dfs(0,-1,0,&ans1);
dfs(N-1,-1,0,&ans2);
if(ans2<ans1)
ans1=ans2;
printf("%lld",ans1);
return 0;
}
void dfs(int x,int y,long long len,long long *ans){
lnode *p;
*ans+=len;
for(p=table[x];p;p=p->next)
if(p->x!=y)
dfs(p->x,x,len+p->w,ans);
return;
}
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;
}
Leave a comment below