Sort by

recency

|

6 Discussions

|

  • + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Zurikela’s Graph Problem Solution

  • + 0 comments

    Here is Zurikela's Graph problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-zurikelas-graph-problem.html

  • + 0 comments

    Python3 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)
    
  • + 3 comments

    why is the example not 7? the 2 nodes in 4 are not connected either?

  • + 1 comment

    Why is the constraint that keeps this problem from becoming NP-Hard hidden like a needle in a haystack?