Codestars. Track 03.

Задача

Немногие знают, что музы существуют на самом деле. Физики-музыковеды выяснили, что музы, как и люди, говорят на разных языках, но это не мешает им общаться. Так, в Секретном институте прикладного музыковедения ученые в ходе наблюдений получили текстовый файл, который в каждой строчке содержит два номера муз (разделенных пробелом), которые общаются друг с другом. Предполагается, что общаются друг с другом только те музы, которые говорят на одном языке, и что для каждой музы в файле есть запись (т.е. муз, которые ни с кем не общаются, не существует).

Узнай, сколько всего языков существует у муз.

Лирическое отступление.

Первый вопрос, который бросился в глаза и ввел меня в недоумение: "А одна муза может говорить только на одном языке? Или они полиглоты?.."
Для начала, предположу, что каждая муза говорит только на одном языке. Просто потому, что я понятия не имею как решать эту задачу в обратном случае.
Тогда, внутри каждого языка существует множество общающихся друг с другом муз. И нам надо найти, всего лишь, количество этих множеств.
Из предположения 1 муза - 1 язык есть два любопытных следствия:

1. Очевидное: множества общающихся муз между языками не пересекаются.
2. Общение понятие транзитивное, т.е. если муза 1 общается с музой 2, но ничего не сказано про общение 1 и 3, но известно, что муза 2 общается с музой 3, то и общение муз 1 и 3 теоретически возможно.

Бонус. Для простоты работы с множествами я буду считать, что общение - штука еще и рефлексивная. Т.е. для каждой музы справедливо, что она общается сама с собой. Ну или просто, что она личность творческая и хранит на первой строчке своей записной книжки свой собственный номер.

Решение.

Для начала я составлю список муз и их контактов.
Муза у нас уникальная и обозначается номером. Так как мне лень каждый раз при сравнении делать Convert.ToInt32() (а еще потому, что называть муз числами как-то грустно, и это могли бы быть имена...) то моя структура для хранения записных книжек муз выглядит так:

Dictionary<string, List<string>> Muses = new Dictionary<string, List<string>>();

В этом словаре ключом выступает имя музы, а в словарь я записываю ее контакты. Начиная с ее собственного.

Теперь у нас для каждой музы есть ее записная книжка. Чтобы узнать количество языков, надо сгруппировать муз, т.е. переписать муз одного языка в одну книжку. Пусть это будет книжка первый встреченной музы данной группы. Искать мы их будем транзитивно - по принципу того, что контакты моего контакта - мои контакты. Берем первую музу и ее контакты (множество М1), для каждого контакта с его контактами (Mi) добавляем различающиеся элементы M1 и Mi.

Как водится у меня есть велосипед (которые мне почему-то очень хочется писать) и адекватный (более менее, наверное) вариант работы с множествами в C#.

Велосипед выглядел как-то так:

for (int i = 0; i < Muses.Keys.Count; i++)
{
    string current_muse = Muses.Keys.ElementAt(i);

    for (int j = 1; j < Muses[current_muse].Count; j++)
    {
string contact_muse = Muses[current_muse][j];
        if (Muses.Keys.Contains(contact_muse))
{
           List<string> except_muses = new List<string>();

            foreach (string transit_muse in Muses[contact_muse])
           {
if (!Muses[current_muse].Contains(transit_muse))
                  Muses[current_muse].Add(transit_muse);  
           }

            Muses.Remove(contact_muse);
}
    }
}

Но где-то здесь надо остановиться. Все что нам на самом деле надо сделать описывается псевдокодом как-то так:

foreach (M1 in M)
{
    foreach (mi in M1)
    {
M1 = M1 + mi; //где "+" - это операция объединения множеств.
M.Remove(mi);
    }
}

Благодаря пространству имен System.Linq любая коллекция в C# поддерживает интерфейс IEnumarable<T>. А он вполне себе множество и имеет такие классные методы как Union, Intersect, Except, where... В общем позволяет вспомнить курс дискретной математики и применить его на практике. Так что мой псевдокод в итоге выглядит так:

for (int i = 0; i < Muses.Keys.Count; i++ )
{
    string current_muse = Muses.Keys.ElementAt(i);

    for (int j = 1; j < Muses[current_muse].Count; j++)
    {
string contact_muse = Muses[current_muse][j];
if (Muses.Keys.Contains(contact_muse))
{
          Muses[current_muse] = Muses[current_muse].Union(Muses[contact_muse]).ToList();
          Muses.Remove(contact_muse);
}
    }
}

Для самых внимательных: итератор foreach не позволяет изменять коллекцию в теле цикла. А мне нужно. Поэтому for.

Проверка на существование contact_muse нужна на случай, если мы записуню книжку этой музы уже обработали.

Вот собственно и все.
Картинка, музычка и проект. )

03_MuseLanguages

Download Muse Starlight for free from pleer.com