Разбиение на группы незнакомых

@Dmitriy1991 · Регистрация: 26.11.2016

Студворк — интернет-сервис помощи студентам

Имеется N человек и матрица A размера N × N. Элемент Aij матрицы равен 1, если человек i знаком с человеком j (если i-й человек знает j-го, то считаем, что и j-й человек знает i-го), и элемент Aij матрицы равен 0, если i-й человек не знаком с человеком j. Можно ли разбить людей на две группы, чтобы в каждой группе были только незнакомые люди (в каждой группе должен быть хотя бы один человек)?

Формат входного файла

Первая строка содержит число N людей (2 ≤ N ≤ 500). Затем идут N строк файла, которые задают матрицу A знакомств (каждой строке матрицы соответствует отдельная строка входного файла, числа в строках разделены пробелами).
Формат выходного файла

Если можно разбить людей на две группы, чтобы в каждой группе были только незнакомые люди, то выведите в первой строке YES, а во второй строке — номера людей (люди нумеруются от 1 до N), которые попали в одну из групп. Числа в строке разделяются одним пробелом и упорядочены по возрастанию. Если разбить нужным образом нельзя, то выведите NO.

input.txt
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
output.txt
YES
1 2

echs · 30.11.2016, 14:49

Dmitriy1991
Разбиение на группы (классы) возможно только тогда
когда выполняются три условия
1. Рефлексивность. Каждый человек знаком сам с собой
2. Симметричность. Если А знаком с Б, то и Б знаком с А
3. Транзитивность. Если А знаком с Б, и Б знаком с В, то
А знаком с В.

@Shamil1 · 30.11.2016, 15:16

echs,
В данной задаче не требуется разбивать на классы. Знакомых людей можно (и нужно) поместить в разные группы.

@ProgJ · 30.11.2016, 15:29

Пусть первый человек будет в первой группе
Тогда всех с кем он знаком нужно отнести во вторую группу
Все, с кем знакомы люди из второй группы, должны вносится в первую группу
и т.д.
Каждый раз проверяем, что новые члены группы не знакомы между собой
Если после выполнения этой процедуры остаются люди, вне групп, то относим одного из них во вторую группу (чтоб она не оказалась пустой) и начинаем добавлять его знакомых, ...

@VTsaregorodtsev · 30.11.2016, 21:54

Dmitriy1991, Задача обратна к классической математической задаче приведения квадратной матрицы к блочно-диагональному виду, с добавочным (но, что важно - последующим, действующим только при анализе матрицы с переставленными строками-столбцами) ограничением (>=2 блока=группы).
В общем, можно взять готовый алгоритм, просто поменяв в нём учёт ненулевых значений на учёт нулевых.
И если выходят 2 или более стоящих на диагонали блока нулей - то гуд.

@ProgJ · 01.12.2016, 10:20

Сообщение от VTsaregorodtsev

И если выходят 2 или более стоящих на диагонали блока нулей - то гуд.

Должно быть точно 2 нулевых квадратных блока на главной диагонали
И что это за алгоритм?

@Shamil1 · 01.12.2016, 12:27

Простейший код для обхода графа в глубину:

C#
1
2
3
4
5
6
7
void dfs(int v, List<int>[] g, int[] used)
{
    used[v] = 1;
    foreach (int i in g[v])
        if (used[i] == 0)
            dfs(i, g, used);
}

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

C#
1
2
3
4
5
6
7
8
9
10
bool dfs(int v, int group, List<int>[] g, int[] used)
{
    used[v] = group;
    foreach (int i in g[v])
        if (used[i] == 0)
            if (!dfs(i, 3 - group, g, used)) return false;
        else if(used[i] == group)
            return false;
    return true;
}

или немного по-другому:

C#
1
2
3
4
5
bool dfs2(int v, int group, List<int>[] g, int[] used)
{
    used[v] = group;
    return !g[v].Any(i => used[i] == group) && g[v].Where(i => used[i] == 0).All(i => dfs2(i, 3 - group, g, used));
}

Конструкция "3 - group" используется для замены 1 на 2, а 2 на 1.

Добавлено через 5 минут
з.ы. Пока в нашем графе остались незакрашенные вершины, запускаем dfs для любой из них.
В итоге получаем разбиение на две группы. Выводим меньшую из них. Если меньшая группа пустая, то выводим "1".

@VTsaregorodtsev · 01.12.2016, 19:13

Сообщение от ProgJ

Должно быть точно 2 нулевых квадратных блока на главной диагонали

Не, таки не обязательно 2.
Может быть и 1, размером со всю матрицу (т.е. >=2). Тогда его можно будет искусственно раскидать любым способом на 2 группы по 1 и более человека.

@ProgJ · 01.12.2016, 20:13

VTsaregorodtsev, а разве 1>=2 ???

@VTsaregorodtsev · 02.12.2016, 23:25

ProgJ, один нулевой блок размером со всю матрицу N*N при N>=2.
Как в первом посте темы.

ЗЫ. Всем. Можно тестировать предлагаемые алгоритмы на абсолютно любых решениях задачи 8 (или любого числа>=2) ферзей. Там все ферзи "незнакомы" друг с другом, соответственно, их можно любым способом разбить на 2 группы. Главное - чтобы алгоритм при этом находил именно решение "yes".
Хотя, конечно, это недостаточный тест.

@_Ivana · 03.12.2016, 09:53

Не по теме:

А можно ссылку на задачу для проверки решения? Поиском почему-то не нашел.

Новые блоги и статьи Все статьи Все блоги /
Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Dmitriy1991 0 / 0 / 0 Регистрация: 26.11.2016 Сообщений: 7

	Разбиение на группы незнакомых 29.11.2016, 20:43. Показов 3419. Ответов 10 Метки нет (Все метки) Имеется N человек и матрица A размера N × N. Элемент Aij матрицы равен 1, если человек i знаком с человеком j (если i-й человек знает j-го, то считаем, что и j-й человек знает i-го), и элемент Aij матрицы равен 0, если i-й человек не знаком с человеком j. Можно ли разбить людей на две группы, чтобы в каждой группе были только незнакомые люди (в каждой группе должен быть хотя бы один человек)? Формат входного файла Первая строка содержит число N людей (2 ≤ N ≤ 500). Затем идут N строк файла, которые задают матрицу A знакомств (каждой строке матрицы соответствует отдельная строка входного файла, числа в строках разделены пробелами). Формат выходного файла Если можно разбить людей на две группы, чтобы в каждой группе были только незнакомые люди, то выведите в первой строке YES, а во второй строке — номера людей (люди нумеруются от 1 до N), которые попали в одну из групп. Числа в строке разделяются одним пробелом и упорядочены по возрастанию. Если разбить нужным образом нельзя, то выведите NO. input.txt 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 output.txt YES 1 2 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	30.11.2016, 14:49
	Dmitriy1991 Разбиение на группы (классы) возможно только тогда когда выполняются три условия 1. Рефлексивность. Каждый человек знаком сам с собой 2. Симметричность. Если А знаком с Б, то и Б знаком с А 3. Транзитивность. Если А знаком с Б, и Б знаком с В, то А знаком с В. 0

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	30.11.2016, 15:16
	echs, В данной задаче не требуется разбивать на классы. Знакомых людей можно (и нужно) поместить в разные группы. 1

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	30.11.2016, 15:29
	Пусть первый человек будет в первой группе Тогда всех с кем он знаком нужно отнести во вторую группу Все, с кем знакомы люди из второй группы, должны вносится в первую группу и т.д. Каждый раз проверяем, что новые члены группы не знакомы между собой Если после выполнения этой процедуры остаются люди, вне групп, то относим одного из них во вторую группу (чтоб она не оказалась пустой) и начинаем добавлять его знакомых, ... 1

@VTsaregorodtsev 2625 / 1636 / 266 Регистрация: 19.02.2010 Сообщений: 4,348
	30.11.2016, 21:54
	Dmitriy1991, Задача обратна к классической математической задаче приведения квадратной матрицы к блочно-диагональному виду, с добавочным (но, что важно - последующим, действующим только при анализе матрицы с переставленными строками-столбцами) ограничением (>=2 блока=группы). В общем, можно взять готовый алгоритм, просто поменяв в нём учёт ненулевых значений на учёт нулевых. И если выходят 2 или более стоящих на диагонали блока нулей - то гуд. 0

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	01.12.2016, 20:13
	VTsaregorodtsev, а разве 1>=2 ??? 0

@VTsaregorodtsev 2625 / 1636 / 266 Регистрация: 19.02.2010 Сообщений: 4,348
	02.12.2016, 23:25
	ProgJ, один нулевой блок размером со всю матрицу N*N при N>=2. Как в первом посте темы. ЗЫ. Всем. Можно тестировать предлагаемые алгоритмы на абсолютно любых решениях задачи 8 (или любого числа>=2) ферзей. Там все ферзи "незнакомы" друг с другом, соответственно, их можно любым способом разбить на 2 группы. Главное - чтобы алгоритм при этом находил именно решение "yes". Хотя, конечно, это недостаточный тест. 0

@_Ivana
	03.12.2016, 09:53
	Не по теме: А можно ссылку на задачу для проверки решения? Поиском почему-то не нашел. 0