I want to solve this problem by DSU.. But,unfortunately,i don't get that..i have already checked Tutorial,someone else code..but,till now,i'm in darkness It's an Bipartite graph base problem.But,what is happening here ? Anyone plz help me. Thanks in advance
See the graph as a group of people who can speak to each other and you will get it :)
speak to each other means "anyone can speak with anyone",doesn't it?
Exactly!
if u want to use DSU, here is my approach: (i use 0 based index)
first, i make a vector of vector, lang[i] contains the data of people who can speak languange i. then i just iterate trouht all the vectors, if a and b can speak the same languange they must belong to the same group, so we union them. so lets say a and b can speak languange i, so we union a and b, now lets say a and c can speak languange j, so we union a and c, so now their group looks like {a,b,c}, each of the group's member can correspondes with one another.
after we do al the operations, the answer is the number of different components minus 1, because we can ask a member of a group to study one languange spoken by the other group, so we keep a variable component, which is iniatially n, and everytime we successfully do a union() operation, we decrease the counter by 1, (because the number of components is decreased by 1).
also theres a special case where nobody can speak any languange...
my code: http://codeforces.net/contest/277/submission/20078985