Ehsan_sShuvo's blog

Need Help for an easiest problem on DSU

By Ehsan_sShuvo, history, 8 years ago, In English

277A - Learning Languages

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

See the graph as a group of people who can speak to each other and you will get it :)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/277/submission/20078985

→ Reply