PROBLEM LINK:Author: Lewin Gan DIFFICULTY:EasyMedium PREREQUISITES:Graphs PROBLEM:Find a maximum subset of nodes such that each node has at least two neighbors of different colors. QUICK EXPLANATION:Remove nodes that cannot be part of any interesting subset, and repeat. EXPLANATION:Let's call a vertex "bad" if all its neighbors are the same color. Obviously, we can't have any bad vertices in our interesting subset, so let's remove them from the graph. This might introduce some more bad vertices, but we can keep repeating this process (this is illustrated in the last sample case). Now, if we have no bad vertices, we claim that the subset is interesting. Of course, this follows from the definition of an interesting subset. What about maximum size? Well, we only removed vertices that had no way of being part of an interesting subset. Thus, we must have a subset of maximum size at the end since we never removed something that could be part of an interesting subset. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Mar, 20:12

i couldn't understand the editorial properly problem says that color/a number is assigned to an edge.but editorial says that fiind neighbour node of different color!!! anyone please explain editorial answered 20 Mar, 12:48

@forhadsidhu neigbour, since the graph is a complete graph . answered 20 Mar, 12:52

@daljit1 actually i couldn't understand the editorial.is it possiblem to explain what u underrstood?? answered 20 Mar, 12:56

We needed to find subset of veriticies so that all of them had edges from them not of same colour. If any vertex had all the edges from it of same colour to all vetricies in the subset, then such a vetrex is termed bad.So, keep removing bad vertices from the graph. Try solving the last test case given the examples. answered 20 Mar, 14:40
