Блог пользователя Ehsan_sShuvo

Автор Ehsan_sShuvo, история, 8 лет назад, По-английски

277A - Изучение языков

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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