help me
#Non adjacent graph maximum sum nodes undirected cyclic graph
gilded solar
What’s the question
sterile basin
you're given an undirected graph that can have a cycle
you have to choose a group of nodes that
- none of the nodes in the group are connected
- sum of the values on the node is maximal
there's always a correct answer because a group that has 1 node is possible
this is hard because the graph can contain a cycle
with a cyclic node group that has an odd number of nodes (more than 1), there can be more than 2 groups so we can't do the normal graph coloring
gilded solar
Do you still need help? I’m just seeing this
sterile basin
yeah i do (:
gilded solar
I think a DFS traversal of the graph starting from each node could work
At each node, there will be 2 options to consider. 1.) including the current node in the group & then recursively exploring its neighbors while making sure none of them are in the group. 2.) excluding the current node and recursively exploring its neighbors.
Keep track of the maximum achievable sum for each group that satisfies the conditions and once the DFS traversal is complete, return the maximum sum found among all the valid groups
This approach should essentially make sure that you explore all possible combinations while observing the constraints
Idk if this is what you’re looking for exactly but just ping me if you need me to clarify or explain in a different way.