can anyone help me to find two node that are not adjacent to each other but has highest degree.
suppose node 1 with 4 degree, node 5 with 4 degree but node 1 and 5 are adjacent so we cant choose node 1 and 5. another node 8 has a degree of 3. and all other node has degree <= 3. also node 5 and 8 are not adjacent, so we can choose node 1 and 8, or 5 and 8. I did not come up with any idea so seeking for help
Is this in reference to Recent Div2C Remove Exactly Two ?? If so, then sort the nodes by degree (in decreasing order) and then check for every pair whether they are adjacent or not by applying Binary Search on Adjacency List..
Although, we can check for adjacency in O(1) also by storing parents (using DFS or whatever approach you like) and then Nodes U and V are adjacent if Parent(U) == V or Parent(V) == U.
Hope it helps ??
Store the degrees of each node in an array. Get the index of the node with the maximum degree. Now, traverse through the adjacency list of that node and mark every node visited. Now, get the second node with the highest degree among the unvisited nodes.