Разобраться в коде

03.05.2020, 14:09. Показов 492. Ответов 0

Метки нет (Все метки)

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

Не могу понять как работает метод dfs

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
35
using namespace std;
 
vector<int> graph[100000];
char color[100000];     //Цвет будем представлять типом char
                        //0 - вершина ещё не покрашена; 1, 2 - различные цвета.
 
inline char invert(int c) {
    return c == 1 ? 2 : 1;
}
 
void dfs(int v, char c) {   //c - цвет текущей вершины
    color[v] = c;
 
    for (int u: graph[v]) {
        if (color[u] == 0) {    //непосещённая вершина
            dfs(u, invert(c));
        } else if (color[u] == c) {
            cout << "Graph is not bipartite." << endl;
            exit(0);
        }
    }
}
 
int main() {
    //Ввод графа...
 
    //Двудольный граф может быть несвязным (тогда существуют несколько способов покраски).
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            dfs(i, 1);
        }
    }
 
    cout << "Graph is bipartite." << endl;
}

IT_Exp

Эксперт

34794 / 4073 / 2104

Регистрация: 17.06.2006

Сообщений: 32,602

Блог

03.05.2020, 14:09

Ответы с готовыми решениями:

Разобраться в коде
Алгоритм сортирует элементы матрицы согласно схеме (см. изображение), в порядке убывания и методом пузырька. Происходит движение: 1) вниз...

Разобраться в коде
#include <iostream> #include <math.h> #define n 3 int m = { -3; 6; -5; 1; 2; -9; 0; 4; -3 }; int main() { int i, j, q, h, w =...

Разобраться в коде
$(function () { Register.initialize({ formId: '#register-form', registerBtnId: '#registerBtn', ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

BasicMan

Эксперт

29316 / 5623 / 2384

Регистрация: 17.02.2009

Сообщений: 30,364

Блог

03.05.2020, 14:09

Помогаю со студенческими работами здесь

Разобраться в коде
https://msdn.microsoft.com/en-us/library/debx8sh9%28v=vs.110%29.aspx Помогите объяснить работу этого кода, чтоыб его можно было...

Разобраться в коде
Здравствуйте, только начал изучать Java , нашел интересный для меня код на зарубежном ресурсе , но что то мне не удается в нем разобраться,...

Разобраться в коде на С
Я написал код, в котором значения функций должны выводиться в таблицу, но они выводяться за пределы таблицы, как сделать так чтобы они были...

Разобраться в коде
Здраствуйте. Может кто нибуть мне помочь обьяснить что означает вот етот код: $("#button").click( function(event){ ...

разобраться в коде
доброго времени суток, всем. так сложилось что на курсовую задали программу, написание которой нам впредь не объясняли никогда, даже...

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

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

Наверх