Issues with my graph theory solution(easy)

general
,
1

Hello guys,I was doing this graph theory problem which requires simple bfs.I have few issues with this hope you can help me out.

P.S-I have seen its solution on web and I cannot understand why we are doing bfs from every node?? And summing maximum of red and black everytime.Please see my solution v/s one i found in web.Thank you

2

The error in your code is that you are not marking your initial x as 1. Do, vis[x]=1 before starting your bfs traversal. It should possibly work after this.

The input you are given is not in any necessary sequential order. I.e consider 3 fights between where u and v are:

4 5
1 2
2 3

How are you supposed to reach 4 in this bfs traversal of yours? Your code will start from 2. Reach 3 and 1 and will give 2 as the answer. There’s no way you reached for the fight between 4 and 5. So, for this purpose, we keep a loop in main() this manner:

for(int i=1;i<=max_n;i++){
  if(color[i]== INVALID_ENTRY)
   {
      // this signifies that the node i has not been included in any bfs traversal till now
      bfs(i);
   }
  else if(color[i]==1 || color[i]==0)
   continue;
 // as valid entry as per your code is 0 or 1. So, keep something like -1 for invalid color and identifying that the nde has not been visited.
}

However, you can simply do a if(vis[i]==0) check instead of the color check above.

1 Like
3

anyone please…i am stuck ??

4

@damn_me How did you come to know that the graph is “disjoint”,just by seeing test cases?

5

Input doesn’t say that you’ll be given connected graph. We manipulated the problem in terms of that. Lets say, you have an array based question, what possible test cases come to your mind often? Possibly, array has zeroes,+ve and -ve numbers etc. Similarly, for graph, I think the input given is connected or not is a very common case which is usually missed :stuck_out_tongue:

1 Like
6

Ok.Got it…As the given graph is not connected therefore I have to run through all elements till MAX_SIZE.Can i use set here to keep track of only used elements ?Will this Improve complexity lil bit ??

7

What are you trying to insert in set? Set stores only unique elements in sorted order. If you thinking that inserting them in set and then replacing the above for loop(iterating till MAX) with iterating over the set elements, there’ll not be any improvement I suppose. Because, in above, only if our condition (color[i]==invalid) comes true, we then we go for bfs. Now, if there’s no entry for that i’th person, function call bfs will return there only as its adj[i].size() will be zero. So, we aren’t computing anything, so optimizing it is “your choice” kind of thing.

1 Like