Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
AVIK
13 / 13 / 6
Регистрация: 02.01.2014
Сообщений: 60
1

Поиск циклов в графе

29.10.2015, 21:47. Просмотров 752. Ответов 6
Метки нет (Все метки)

Подскажите, пожалуйста, какие идеи нужно применять к данной задаче
Любовный многоугольник
Time limit = 5 секунд

Любовный многоугольник — это множество людей S, размер которого больше 2, в котором каждый любит только одного человека из S и эти "любови" образуют один цикл. Другими словами, любовный многоугольник — это цикл без диагоналей.
Дано описание "любовей" для некоторого множества людей. Найдите, есть ли там любовные многоугольники и если есть, выведите размер максимального из них.

Вход В первой строчке количество 'любовей' M, 1 ≤ M ≤ 500. Затем M строчек c описанием, кто кого любит. Строчка

XXXX YYYY

Означает, что XXXX любит YYYY. У разных людей разные имена — cлова в алфавите A..Za..z из менее чем 21 буквы.

Один может любить многих.

Выход Размер любовного максимального многоугольника. Выведите 0 если любовного многоугольника не существует.

Вход#1
6
Kolya Olya
John Jessy
Jessy Kolya
Misha Olya
Olya John
Misha Jessy
Выход#1
4

Вход#2
2
Kolya Olya
Olya Kolya
Выход#2
0
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.10.2015, 21:47
Ответы с готовыми решениями:

Алгоритм поиска элементарных циклов в неориентированном графе
Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри...

Поиск в графе
Здравствуйте, есть следующая задача: Дан массив A длины (n+1), содержащий натуральные числа от 1...

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому существующему ребру...

Поиск путей в графе
Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых множество вершин...

Поиск в ширину в графе
У меня есть небольшая база данных(обычный текстовый файл). Парсирую этот файл и полчается список...

6
Shamil1
Модератор
2304 / 1598 / 358
Регистрация: 26.03.2015
Сообщений: 5,815
30.10.2015, 02:05 2
Сначала добавить все пары в словарь. Если ключ уже есть в словаре, то не добавляем.
А затем искать многоугольник, начиная с любого ключа в словаре. Удаляя использованные ключи из словаря.
0
AVIK
13 / 13 / 6
Регистрация: 02.01.2014
Сообщений: 60
30.10.2015, 10:06  [ТС] 3
Процесс поиска многоугольника совсем нетривиален, он-то меня и интересует.
0
Shamil1
Модератор
2304 / 1598 / 358
Регистрация: 26.03.2015
Сообщений: 5,815
30.10.2015, 11:59 4
В чём нетривиальность? Для текущего имени ищем его любовь, которая становится текущем именем. И так далее идём по цепочке, пока она не оборвётся или не зациклится.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int Solve(IEnumerable<string> input)
{
    Dictionary<string,string> loves = new Dictionary<string,string>();
    foreach(string line in input)
    {
        int pos = line.IndexOf(' ');
        string key = line.Substring(0, pos).Trim();
        if(loves.Keys.Contains(key))
            continue;
        string value = line.Substring(pos + 1).Trim();
        loves.Add(key, value);
    }
    
    int maxLength = 0;
    HashSet<string> used = new HashSet<string>();
    foreach(string key in loves.Keys)
    {
        used.Clear();
        string name = key;
        for(int len = 1; loves.TryGetValue(name, out name); len++)
        {
            if(name == key) // цикл найден
            {
                if(len > maxLength)
                    maxLength = len;
                break; 
            }
            if(used.Contains(name)) // нет цикла
                break;
            used.Add(name);
        }
    }
    return maxLength;
}
Код можно оптимизировать. Например, удалять из словаря имена, используемые в найденных циклах, и т.п.
0
AVIK
13 / 13 / 6
Регистрация: 02.01.2014
Сообщений: 60
30.10.2015, 12:34  [ТС] 5
Цитата Сообщение от Shamil1 Посмотреть сообщение
В чём нетривиальность? Для текущего имени ищем его любовь, которая становится текущем именем. И так далее идём по цепочке, пока она не оборвётся или не зациклится.
https://yadi.sk/i/wvE7TizWk7qDK и что ваш алгоритм будет делать на таком графе любовей?
1
Shamil1
Модератор
2304 / 1598 / 358
Регистрация: 26.03.2015
Сообщений: 5,815
30.10.2015, 12:48 6
Я неправильно понял условие.
0
AVIK
13 / 13 / 6
Регистрация: 02.01.2014
Сообщений: 60
01.11.2015, 21:04  [ТС] 7
Вопрос еще актуален
0
01.11.2015, 21:04
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2015, 21:04

Поиск критических элементов в графе
Критической вершиной в графе называется вершина, удаление которой приводит к разделению графа на 2...

Поиск кратчайшего пути в графе
Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя заданными вершинами в...

Поиск циклов в орграфе
Добрый день! Помогите, пожалуйста, разобраться с задачей. Имеется ориентированный граф....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru