We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Zurikela's Graph
  5. Discussions

Zurikela's Graph

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 4 Discussions, By:

votes

Please Login in order to post a comment

  • liuboying
    5 years ago+ 3 comments

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

    8|
    Permalink
  • TChalla
    1 year ago+ 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)
    
    1|
    Permalink
  • laiden
    5 years ago+ 1 comment

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

    0|
    Permalink
  • Learn12345
    5 years ago+ 1 comment

    Can any one tell me what is the independent nod means?

    0|
    Permalink

No more comments

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature