e-olymp 2270. Поиск цикла

02/12/2019 by Наташа Писаревская

Задача

Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.

Входные данные

В первой строке находятся два натуральных числа $n$ и $m$ $($$1$ $\leqslant$ $n$ $\leqslant$ $10$^$5$$, $$1$ $\leqslant$ $m$ $\leqslant$ $10$^$5$$)$ — количество вершин и ребер в графе соответственно. Далее в $m$ строках перечислены рёбра графа. Каждое задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Выходные данные

Если в графе нет цикла, то вывести «NO», иначе вывести «YES» и затем перечислить вершины в порядке обхода цикла.

Тесты

№	Входные данные	Выходные данные
1	2 2 1 2 1 2	NO
2	2 2 1 2 2 1	YES 1 2
3	6 7 1 2 1 5 2 3 2 4 4 6 6 5 5 2	YES 2 4 6 5
4	6 6 1 3 2 4 3 4 1 2 3 5 3 6	NO
5	4 4 1 3 4 2 2 3 3 4	YES 3 4 2

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph; 
vector<int> used, path;
int flag, n, m;
// поиск в глубину для каждой вершины
void dfs (int v) {
    if (flag == 1) return; // если уже нашли цикл, то останавливаемся
    else {
        used[v] = 1; // посещаем вершину 
        path.push_back(v); // добавляем ее в порядок обхода графа
        for (int i = 0; i < graph[v].size(); i++) {
            int to = graph[v][i];// следующая вершина графа
            if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл
                path.push_back(to); // добавляем следующую вершину в порядок обхода графа
                flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся
                return;
            } 
            else {
                dfs(to); // если не посетили, то посещаем 
            }
            if (flag == 1) return; // если нашли цикл, то останавливаемся 
        }
        used[v] = 2; // если не нашли цикл, то выходим из вершины 
        path.pop_back();
    }
} 
// проверяем вершины на наличие цикла 
void checkNodes() { 
    for (int i = 1; i <= n; i++) {
        if (used[i] == 0) { // если не посещали вершину, то посещаем ее 
            dfs(i);
            if (flag == 1) return; // если нашли цикл, то останавливаемся
        }   
    }
} 
int main(){
    int v1, v2; 
    cin >> n >> m; // считываем количество вершин и ребер 
    graph.resize(n + 1); 
    used.resize(n + 1, 0);
    for (int i = 0; i < m; i++) {
        cin >> v1 >> v2; // считываем ребра и заполняем граф
        graph[v1].push_back(v2);
    }
    checkNodes();  // проверяем вершины на наличие цикла
    if (flag == 1) { // если цикл найден
        int i = path.size() - 2; // последняя вершина цикла   
        int to = path.back(); // вершина в которой зациклились 
        while (path[i] != to) { // получаем индекс вершины в которой зациклились
            i--;
        }
        cout << "YES" << endl;
        while (i < path.size() - 1) { // выводим сам цикл
            cout << path[i] << " ";
            i++; 
        }
        cout << endl;
    }
    else cout << "NO" << endl;
}

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int>> graph;

vector<int> used, path;

int flag, n, m;

// поиск в глубину для каждой вершины

void dfs (int v) {

if (flag == 1) return; // если уже нашли цикл, то останавливаемся

else {

used[v] = 1; // посещаем вершину

path.push_back(v); // добавляем ее в порядок обхода графа

for (int i = 0; i < graph[v].size(); i++) {

int to = graph[v][i];// следующая вершина графа

if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл

path.push_back(to); // добавляем следующую вершину в порядок обхода графа

flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся

return;

}

else {

dfs(to); // если не посетили, то посещаем

}

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

used[v] = 2; // если не нашли цикл, то выходим из вершины

path.pop_back();

}

// проверяем вершины на наличие цикла

void checkNodes() {

for (int i = 1; i <= n; i++) {

if (used[i] == 0) { // если не посещали вершину, то посещаем ее

dfs(i);

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

int main(){

int v1, v2;

cin >> n >> m; // считываем количество вершин и ребер

graph.resize(n + 1);

used.resize(n + 1, 0);

for (int i = 0; i < m; i++) {

cin >> v1 >> v2; // считываем ребра и заполняем граф

graph[v1].push_back(v2);

}

checkNodes(); // проверяем вершины на наличие цикла

if (flag == 1) { // если цикл найден

int i = path.size() - 2; // последняя вершина цикла

int to = path.back(); // вершина в которой зациклились

while (path[i] != to) { // получаем индекс вершины в которой зациклились

i--;

}

cout << "YES" << endl;

while (i < path.size() - 1) { // выводим сам цикл

cout << path[i] << " ";

i++;

}

cout << endl;

}

else cout << "NO" << endl;

}

Решение

Для решения данной задачи воспользуемся поиском в глубину. Также будем отмечать вершины в различными цветами ($0$ (белый) — мы еще не посещали вершину, $1$ (серый) — посетили вершину и не вышли из нее (зациклились), $2$ (черный) — посетили вершину и вышли из неё).

В векторе $graph$ будем хранить сам граф, для проверки на цикличность воспользуемся вектором $visited$, так же будем хранить порядок обхода графа в векторе $path$. Так как по условию, в случае нескольких циклов, необходимо вывести любой, то мы будем находить первый и на этом останавливаться, для этого заведем переменную $flag$, которая равна 1, если цикл уже найден, и равна 0, если цикл еще не найден. В векторе $visited$ будем окрашивать вершину в один из цветов. Если мы захотим посетить $1$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине, тогда устанавливаем $flag = 1$.

Осталось лишь вывести его на экран. Для этого воспользуемся вектором $path$, в котором последний элемент — вершина, в которой цикл. Ищем предпоследнее вхождение этой вершины в векторе $path$ и выводим сам цикл.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Related Images:

Алгоритмы поиска

16/11/2019 by Мазурок Игорь Евгеньевич

Search Algorithms

Хочу предложить простой, но достаточно общий взгляд на алгоритмы поиска в ширину BFS (Breadth-first Search), в глубину DFS (Depth-first Search) и бесконечное количество других с общей схемой. Фактически это алгоритмы обхода соседних вершин графа в которых последовательно строятся пути из некоторой исходной вершины ко всем остальным.
Сначала сформулируем общую схему алгоритмов этого типа. И без обычных для учебников избыточных сложностей в виде белых-серых-черных вершин.

Заводим PLAN поиска — контейнер данных, где будем хранить вершины в которых мы планируем побывать. Изначально он пуст.
Добавляем в PLAN поиска исходную вершину с которой нам предписано начать.
Пока PLAN не пуст и цель поиска не достигнута делаем следующее
1. GET: Извлекаем из PLAN какую-нибудь вершину v.
2. Посещаем вершину v. Если мы не просто обходим вершины, а что-то ищем, то здесь самое время обыскать вершину v на предмет достижения цели поиска.
3. Как-то отмечаем, что вершина v уже посещена.
4. PUT: Добавляем в PLAN все соседние с v вершины, которые еще не были посещены.
Выводим результат поиска.

Самым важным для реализации этой схемы является PLAN. Это контейнер данных в котором нам нужны две функции GET — чтобы что-то из контейнера достать и PUT — чтобы в контейнер что-то положить. Конечно лучше использовать уже готовые контейнеры. Выбор контейнера будет определять стратегию поиска.
DFS (Depth-first Search). Например, если в качестве контейнера выбрать СТЕК, то мы реализуем алгоритм поиска в глубину. Ведь организация доступа к элементам стека такова, что мы в первую очередь будем посещать те вершины, которые попали в план последними. Посмотрим на код решения задачи
Обход в глубину:

#include <iostream>
#include <stack>
using namespace std;
int main() {
    // чтение исходных данных
    int n, v;
    cin >> n >> v;
    int matrix[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    stack <int> plan; // план посещения в виде стека
    plan.push(--v);   // мы нумеруем с 0, а не с 1
    matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план 
    int counter = 1;  // начальную уже сосчитали
    while (!plan.empty()) {
        v = plan.top(); // посещаем следующую по плану вершину 
        plan.pop();       // удаляем ее из плана посещения
        for (int u = 0; u < n; u++) { // перебираем соседние с ней
            if (matrix[v][u] and !matrix[u][u]) { // если новая, то
                plan.push(u);     // добавляем ее в план
                matrix[u][u] = 1; // отмечаем, что уже не новая
                counter++;        // считаем, сколько было вершин
            }
        }
    }
    cout << counter << endl;
}

#include <iostream>

#include <stack>

using namespace std;

int main() {

// чтение исходных данных

int n, v;

cin >> n >> v;

int matrix[n][n];

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

cin >> matrix[i][j];

stack <int> plan; // план посещения в виде стека

plan.push(--v); // мы нумеруем с 0, а не с 1

matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план

int counter = 1; // начальную уже сосчитали

while (!plan.empty()) {

v = plan.top(); // посещаем следующую по плану вершину

plan.pop(); // удаляем ее из плана посещения

for (int u = 0; u < n; u++) { // перебираем соседние с ней

if (matrix[v][u] and !matrix[u][u]) { // если новая, то

plan.push(u); // добавляем ее в план

matrix[u][u] = 1; // отмечаем, что уже не новая

counter++; // считаем, сколько было вершин

}

cout << counter << endl;

}

Единственное важное пояснение. Чтобы отметить, что вершина уже посещалась, я использую диагональ матрицы смежности графа. в условии специально подчеркнули, что там всегда нули, а значит я могу поставить matrix[v][v] = 1, чтобы обозначить вершину v как уже посещенную.

BFS (Breadth-first Search). Стоит нам немного изменить код и использовать для хранения плана ОЧЕРЕДЬ, алгоритм меняет стратегию и осуществляет поиск в ширину. Поскольку вершины будут посещаться в том порядке в котором мы их добавляли, это очень похоже на распространение волны из начальной точки. Отсюда другое название таких алгоритмов — заливки (flood) или волновые алгоритмы.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // чтение исходных данных
    int n, v;
    cin >> n >> v;
    int matrix[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    queue <int> plan; // план посещения в виде очереди
    plan.push(--v);   // мы нумеруем с 0, а не с 1
    matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план 
    int counter = 1;  // начальную уже сосчитали
    while (!plan.empty()) {
        v = plan.front(); // посещаем следующую по плану вершину 
        plan.pop();       // удаляем ее из плана посещения
        for (int u = 0; u < n; u++) { // перебираем соседние с ней
            if (matrix[v][u] and !matrix[u][u]) { // если новая, то
                plan.push(u);     // добавляем ее в план
                matrix[u][u] = 1; // отмечаем, что уже не новая
                counter++;        // считаем, сколько было вершин
            }
        }
    }
    cout << counter << endl;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

// чтение исходных данных

int n, v;

cin >> n >> v;

int matrix[n][n];

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

cin >> matrix[i][j];

queue <int> plan; // план посещения в виде очереди

plan.push(--v); // мы нумеруем с 0, а не с 1

matrix[v][v] = 1; // отмечаем, что эта вершина уже заносилась в план

int counter = 1; // начальную уже сосчитали

while (!plan.empty()) {

v = plan.front(); // посещаем следующую по плану вершину

plan.pop(); // удаляем ее из плана посещения

for (int u = 0; u < n; u++) { // перебираем соседние с ней

if (matrix[v][u] and !matrix[u][u]) { // если новая, то

plan.push(u); // добавляем ее в план

matrix[u][u] = 1; // отмечаем, что уже не новая

counter++; // считаем, сколько было вершин

}

cout << counter << endl;

}

Если для хранения плана написать свой контейнер или хотя бы переопределить методы GET и PUT, то вы получите новый алгоритм поиска. Например, можно извлекать вершину из плана случайным образом. В этом случае мы получим один из рандомизированных алгоритмов семейства Монте-Карло.

Задание: Найдите все четыре места, где код поиска в глубину отличается от кода поиска в ширину.
Подсказка: Если не смогди найти четвертое отличие — оно в комментариях 🙂

Related Images:

e-olymp 4000. Обход в глубину

05/06/2018 by Кирилл Волков

Задача

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

Входные данные

В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные

Выведите искомое количество вершин.

Тесты

Входные данные	Выходные данные
3 1 0 0 1 0 0 0 1 0 0	2
4 2 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0	4
6 2 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0	3
4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	1
5 3 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0	5

Код программы

#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>

using namespace std;

void dfs(int cur, vector<vector<int>> & adj, vector<bool> & was, int & count){
    if(!was[cur]){
        was[cur] = true;
        count++;
        for(int i = 0; i < adj[cur].size(); i++){
            dfs(adj[cur][i], adj, was, count);
        }
    }
}

int getCount(int start, vector<vector<int>> & adj){
    vector<bool> was(adj.size(), false);
    int count = 0;
    dfs(start, adj, was, count);
    return count;
}

int main() {
    int n;
    cin >> n;
    int start;
    cin >> start;
    start--;
    vector<vector<int>> adj(n, vector<int>());
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int temp;
            cin >> temp;
            if(temp == 1){
                adj[i].push_back(j);
            }
        }
    }
    cout << getCount(start, adj);
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

#include <vector>

using namespace std;

void dfs(int cur, vector<vector<int>> & adj, vector<bool> & was, int & count){

if(!was[cur]){

was[cur] = true;

count++;

for(int i = 0; i < adj[cur].size(); i++){

dfs(adj[cur][i], adj, was, count);

}

int getCount(int start, vector<vector<int>> & adj){

vector<bool> was(adj.size(), false);

int count = 0;

dfs(start, adj, was, count);

return count;

}

int main() {

int n;

cin >> n;

int start;

cin >> start;

start--;

vector<vector<int>> adj(n, vector<int>());

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

int temp;

cin >> temp;

if(temp == 1){

adj[i].push_back(j);

}

cout << getCount(start, adj);

return 0;

}

Решение задачи

Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа $c$ будет искомым числом.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 88. Месть Ли Чака

04/02/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

Входные данные

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

Выходные данные

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

Код программы

#include <iostream>
#include <vector>

using  namespace std;

const int INF = 10000000;
const string GAYBRASH = "GAYBRASH";
const string LICHACK = "LICHACK";

struct node{
    int x;
    int y;
};

vector<node> getChildrenBFS(char ** map, node parent, string hero){
    string bannedChars = "R";
    if(hero == LICHACK) bannedChars.push_back('e');
    vector<node> children;
    node leftChild = {parent.x - 1, parent.y};
    node rightChild = {parent.x + 1, parent.y};
    node downChild = {parent.x, parent.y + 1};
    node upChild = {parent.x, parent.y - 1};
    if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){
        children.push_back(leftChild);
    }
    if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){
        children.push_back(rightChild);
    }
    if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){
        children.push_back(downChild);
    }
    if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){
        children.push_back(upChild);
    }
    return children;
}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children) {
        if (move < moves[e.y][e.x]) {
            dfsSecondPlayer(map, moves, hero, e, move);
        }
    }
}
void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){
    moves[currentNode.y][currentNode.x] = move;
    move++;
    vector<node> children = getChildrenBFS(map, currentNode, hero);
    vector<node> queue;
    for(auto e: children){
        if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){
            dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);
        }
    }
}
int main() {
    int tests;
    cin >> tests;
    for(; tests > 0; tests--){
        int m;
        int n;
        cin >> m >> n;
        cin.ignore();
        node g;
        node l;
        node e;
        char **map = new char*[m];
        for(int i = 0; i < m; i++){
            map[i] = new char[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = cin.get();
                switch(map[i][j]){
                    case 'g':
                        g.x = j;
                        g.y = i;
                        break;
                    case 'l':
                        l.x = j;
                        l.y = i;
                        break;
                    case 'e':
                        e.x = j;
                        e.y = i;
                        break;
                }
            }
            cin.ignore();
        }
        int **liChack = new int*[m];
        for(int i = 0; i < m; i++){
            liChack[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                liChack[i][j] = INF;
            }
        }
        dfsSecondPlayer(map, liChack, LICHACK, l, 0);
        int **gaybrash = new int*[m];
        for(int i = 0; i < m; i++){
            gaybrash[i] = new int[n];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                gaybrash[i][j] = INF;
            }
        }
        dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);
        bool OK = gaybrash[e.y][e.x] != INF;
        cout << (OK ? "YES" : "NO") << endl;
        for(int i = 0; i < m; i++){
            delete[] map[i];
        }
        delete[] map;
        for(int i = 0; i < m; i++){
            delete[] gaybrash[i];
        }
        delete[] gaybrash;
        for(int i = 0; i < m; i++){
            delete[] liChack[i];
        }
        delete[] liChack;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

#include <iostream>

#include <vector>

using namespace std;

const int INF = 10000000;

const string GAYBRASH = "GAYBRASH";

const string LICHACK = "LICHACK";

struct node{

int x;

int y;

};

vector<node> getChildrenBFS(char ** map, node parent, string hero){

string bannedChars = "R";

if(hero == LICHACK) bannedChars.push_back('e');

vector<node> children;

node leftChild = {parent.x - 1, parent.y};

node rightChild = {parent.x + 1, parent.y};

node downChild = {parent.x, parent.y + 1};

node upChild = {parent.x, parent.y - 1};

if(bannedChars.find(map[leftChild.y][leftChild.x]) == string::npos){

children.push_back(leftChild);

}

if(bannedChars.find(map[rightChild.y][rightChild.x]) == string::npos){

children.push_back(rightChild);

}

if(bannedChars.find(map[downChild.y][downChild.x]) == string::npos){

children.push_back(downChild);

}

if(bannedChars.find(map[upChild.y][upChild.x]) == string::npos){

children.push_back(upChild);

}

return children;

}

void dfsSecondPlayer(char ** map, int ** moves, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children) {

if (move < moves[e.y][e.x]) {

dfsSecondPlayer(map, moves, hero, e, move);

}

void dfsFirstPlayer(char ** map, int ** moves, int ** secondPlayer, string hero, node currentNode, int move){

moves[currentNode.y][currentNode.x] = move;

move++;

vector<node> children = getChildrenBFS(map, currentNode, hero);

vector<node> queue;

for(auto e: children){

if(move < moves[e.y][e.x] && move < secondPlayer[e.y][e.x]){

dfsFirstPlayer(map, moves, secondPlayer, hero, e, move);

}

int main() {

int tests;

cin >> tests;

for(; tests > 0; tests--){

int m;

int n;

cin >> m >> n;

cin.ignore();

node g;

node l;

node e;

char **map = new char*[m];

for(int i = 0; i < m; i++){

map[i] = new char[n];

}

for(int i = 0; i < m; i++){

for(int j = 0; j < n; j++){

map[i][j] = cin.get();

switch(map[i][j]){

case 'g':

g.x = j;

g.y = i;

break;

case 'l':

l.x = j;

l.y = i;

break;

case 'e':

e.x = j;

e.y = i;

break;

}

cin.ignore();

}

int **liChack = new int*[m];

for(int i = 0; i < m; i++){

liChack[i] = new int[n];

}

for(int i = 0; i < m; i++){

for(int j = 0; j < n; j++){

liChack[i][j] = INF;

}

dfsSecondPlayer(map, liChack, LICHACK, l, 0);

int **gaybrash = new int*[m];

for(int i = 0; i < m; i++){

gaybrash[i] = new int[n];

}

for(int i = 0; i < m; i++){

for(int j = 0; j < n; j++){

gaybrash[i][j] = INF;

}

dfsFirstPlayer(map, gaybrash, liChack, GAYBRASH, g, 0);

bool OK = gaybrash[e.y][e.x] != INF;

cout << (OK ? "YES" : "NO") << endl;

for(int i = 0; i < m; i++){

delete[] map[i];

}

delete[] map;

for(int i = 0; i < m; i++){

delete[] gaybrash[i];

}

delete[] gaybrash;

for(int i = 0; i < m; i++){

delete[] liChack[i];

}

delete[] liChack;

}

return 0;

}

Решение задачи

Предположим, что существует безопасный для Гайбраша маршрут. Это означает, что Ли Чак не может перехватить его ни в одной точке этого маршрута, то есть, что в любую точку маршрута Гайбраш попадает как минимум на один ход раньше, чем Ли Чак. В противном случае безопасного хода нет.
Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. С помощью поиска в глубину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в глубину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае -нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

Код Хаффмана

15/04/2017 by Вадим Гордийчук

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированную строку.

Входные данные

Некоторая последовательность символов и endl.

Выходные данные

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированная строка.

Тест

Входные данные	Выходные данные
MOLOKO KIPIT	digraph G { "'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ]; "'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ]; "'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ]; "'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ]; "'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ]; "'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ]; "' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ]; "' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ]; "' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ]; "' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ]; "'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ]; "'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ]; "'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ]; "'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ]; } Codes of letters: 'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100) Encoded string: 00001001011010110010111011111101110

Входные данные

Выходные данные

MOLOKO KIPIT

digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

Код программы

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

struct ltcode
{
    unsigned long long frequency;
    unsigned char letter;
    string code = "";
};

void zeroset(ltcode *c)
{
    for (unsigned int i = 0; i < 256; ++i)
    {
        c[i].frequency = 0;
        c[i].letter = i;
    }
}

bool f(ltcode x, ltcode y)
{
    if (x.frequency != y.frequency) return x.frequency > y.frequency;
    else return x.letter > y.letter;
}

struct B
{
    string list;
    int i;
    
    int left;
    int right;
    
    string code = "";
    
    B()
    {
        list = "";
        i = 0;
    }
};

void print_binary_tree(int num, vector <B> &tree)
{
    if (tree[num].list.size() > 1)
    {
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";
        print_binary_tree(tree[num].left, tree);
        print_binary_tree(tree[num].right, tree);
    }
}

void print_tree_graph(vector <B> &tree)
{
    cout << "digraph G {\n";
    print_binary_tree(tree.size()-1, tree);
    cout << "}\n";
}

void huffman_encoding_in(int num, string code, vector <B> &tree, ltcode *letter_codes)
{
    tree[num].code = code;
    if (tree[num].list.size() > 1)
    {
        huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);
        huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);
    }
    else
    {
        for (int j = 0; ; ++j)
        {
            if (letter_codes[j].letter == tree[num].list[0])
            {
                letter_codes[j].code = code;
                break;
            }
        }
    }
}

void huffman_encoding(vector <B> &sorted_tree, ltcode *letter_codes)
{
    huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);
}

int main() {
    unsigned char c;
    string S;
    ltcode count[256], stringlinks[256];
    zeroset(count);

    while (scanf("%c", &c))
    {
        if (c == '\n') break;
        S += c;
        ++count[c].frequency;
    }
    sort(count, count+256, f);
    
    vector <B> tree;
    B tmp;
    tmp.list = "0";
    int j = 0, letter_amount;
    for (j = 0; (count[j].frequency); ++j)
    {
        tmp.i = count[j].frequency;
        tmp.list[0] = count[j].letter;
        tree.push_back(tmp);
    }
    int maxsize = j-1, size;
    
    sort(tree.begin(), tree.end(), [] (B a, B b)
    {
        if (a.i != b.i) return (a.i < b.i);
        else return (a.list.size() < b.list.size());
    });
    
    for (j = 0; size < maxsize;)
    {
        tmp.list = tree[j].list + tree[j+1].list;
        tmp.i = tree[j].i + tree[j+1].i;
        tmp.left = j;
        tmp.right = j+1;
        
        size = tmp.list.size();
        
        tree.push_back(tmp);
        j += 2;
        sort(tree.begin()+j, tree.end(), [] (B a, B b)
        {
            if (a.i != b.i) return (a.i < b.i);
            else return (a.list.size() < b.list.size());
        }
        );
    }
    huffman_encoding(tree, count);
    print_tree_graph(tree);
    cout << "\nCodes of letters:\n";
    for (j = 0; (count[j].frequency); ++j)
    {
        cout << '\'' << count[j].letter << "\'(" << count[j].code << ")  ";
        stringlinks[count[j].letter].code = count[j].code;
    }
    cout << "\n\nEncoded string:\n";
    for (unsigned int i = 0; i < S.size(); ++i)
    {
        cout << stringlinks[S[i]].code;
    }
    cout << '\n';
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

struct ltcode

{

unsigned long long frequency;

unsigned char letter;

string code = "";

};

void zeroset(ltcode *c)

{

for (unsigned int i = 0; i < 256; ++i)

{

c[i].frequency = 0;

c[i].letter = i;

}

bool f(ltcode x, ltcode y)

{

if (x.frequency != y.frequency) return x.frequency > y.frequency;

else return x.letter > y.letter;

}

struct B

{

string list;

int i;

int left;

int right;

string code = "";

B()

{

list = "";

i = 0;

}

};

void print_binary_tree(int num, vector &tree)

{

if (tree[num].list.size() > 1)

{

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";

print_binary_tree(tree[num].left, tree);

print_binary_tree(tree[num].right, tree);

}

void print_tree_graph(vector &tree)

{

cout << "digraph G {\n";

print_binary_tree(tree.size()-1, tree);

cout << "}\n";

}

void huffman_encoding_in(int num, string code, vector &tree, ltcode *letter_codes)

{

tree[num].code = code;

if (tree[num].list.size() > 1)

{

huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);

huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);

}

else

{

for (int j = 0; ; ++j)

{

if (letter_codes[j].letter == tree[num].list[0])

{

letter_codes[j].code = code;

break;

}

void huffman_encoding(vector &sorted_tree, ltcode *letter_codes)

{

huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);

}

int main() {

unsigned char c;

string S;

ltcode count[256], stringlinks[256];

zeroset(count);

while (scanf("%c", &c))

{

if (c == '\n') break;

S += c;

++count[c].frequency;

}

sort(count, count+256, f);

vector tree;

B tmp;

tmp.list = "0";

int j = 0, letter_amount;

for (j = 0; (count[j].frequency); ++j)

{

tmp.i = count[j].frequency;

tmp.list[0] = count[j].letter;

tree.push_back(tmp);

}

int maxsize = j-1, size;

sort(tree.begin(), tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

});

for (j = 0; size < maxsize;)

{

tmp.list = tree[j].list + tree[j+1].list;

tmp.i = tree[j].i + tree[j+1].i;

tmp.left = j;

tmp.right = j+1;

size = tmp.list.size();

tree.push_back(tmp);

j += 2;

sort(tree.begin()+j, tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

}

);

}

huffman_encoding(tree, count);

print_tree_graph(tree);

cout << "\nCodes of letters:\n";

for (j = 0; (count[j].frequency); ++j)

{

cout << '\'' << count[j].letter << "\'(" << count[j].code << ") ";

stringlinks[count[j].letter].code = count[j].code;

}

cout << "\n\nEncoded string:\n";

for (unsigned int i = 0; i < S.size(); ++i)

{

cout << stringlinks[S[i]].code;

}

cout << '\n';

return 0;

}

Решение задачи

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.

После этого, используя поиск в глубину, кодируем элементы массива tree, начиная с последнего (строка которого в результате использования алгоритма всегда оказывается объединением всех символов). Остальная часть решения поставленной задачи — вопрос техники.

Ссылки

Код программы на ideone.com.

Related Images:

e-olymp 1948. Топологическая сортировка

06/06/2016 by Грешилов Константин

Условие:
Дан ориентированный невзвешенный граф. Необходимо топологически отсортировать его вершины.

Входные данные

В первой строке содержатся количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100000) и количество рёбер [latex]m[/latex] (1 ≤[latex]m[/latex] ≤ 100000) в графе. В следующих [latex]m[/latex] строках перечислены рёбра графа, каждое из которых задаётся парой чисел — номерами начальной и конечной вершины.

Выходные данные

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, то вывести -1.

Тесты:

Входные данные	Выходные данные
6 6 1 2 3 2 4 2 2 5 6 5 4 6	4 6 3 1 2 5
2 2 1 2 2 1	-1
4 5 1 2 1 3 3 4 2 4 1 4	1 3 2 4
4 5 1 2 1 3 3 4 2 4 4 1	-1

Решение:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность
    color[v] = 1;
    for (size_t i = 0; i < graph[v].size(); ++i) {
        int to = graph[v][i];
        if (color[to] == 0) { //если в вершину не входили ни разу
            if (cyclic (to, cycle_st, graph,  color))  return true;
        }
        else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл
            cycle_st = to; // и меняем значение индикатора 
            return true; 
        }
    }
    color[v] = 2; //указываем, что в вершину больше ни разу входить не будем
    return false;
}
void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    used[v] = true; //указываем, что использовали данную вершину
    for (int i=0; i < graph[v].size(); i++) {
        int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v
        if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё
            dfs (to, graph, used, answer);
    }
    answer.push_back (v+1); // заносим вершину в вектор, хранящий результат
}
 
void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована
        used[i] = false;
    for (int i = 0; i < n; i++)
        if (!used[i]) //если в ходе предыдущий операций вершина не использовалась
            dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину
    reverse (answer.begin(), answer.end());
}

int main() {
    int n, m; // число вершин и ребер
    cin >> n >> m;
    int a, b;
    vector <int> graph[100001]; // граф
    vector <bool> used (n);
    vector<int> answer;
    vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.
    int cycle_st = -1;
    for (int i = 0; i < m; i++){
            cin >> a >> b;
            graph[a-1].push_back(b-1);
        }
    for (int i = 0; i < n; i++){
        if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность
            break;
    }
    if (cycle_st != -1){ 
        cout << "-1";
    }
    else{
        topological_sort(n, graph, used, answer);
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i] << " "; 
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность

color[v] = 1;

for (size_t i = 0; i < graph[v].size(); ++i) {

int to = graph[v][i];

if (color[to] == 0) { //если в вершину не входили ни разу

if (cyclic (to, cycle_st, graph, color)) return true;

}

else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл

cycle_st = to; // и меняем значение индикатора

return true;

}

color[v] = 2; //указываем, что в вершину больше ни разу входить не будем

return false;

}

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

used[v] = true; //указываем, что использовали данную вершину

for (int i=0; i < graph[v].size(); i++) {

int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v

if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё

dfs (to, graph, used, answer);

}

answer.push_back (v+1); // заносим вершину в вектор, хранящий результат

}

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована

used[i] = false;

for (int i = 0; i < n; i++)

if (!used[i]) //если в ходе предыдущий операций вершина не использовалась

dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину

reverse (answer.begin(), answer.end());

}

int main() {

int n, m; // число вершин и ребер

cin >> n >> m;

int a, b;

vector <int> graph[100001]; // граф

vector <bool> used (n);

vector<int> answer;

vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.

int cycle_st = -1;

for (int i = 0; i < m; i++){

cin >> a >> b;

graph[a-1].push_back(b-1);

}

for (int i = 0; i < n; i++){

if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность

break;

}

if (cycle_st != -1){

cout << "-1";

}

else{

topological_sort(n, graph, used, answer);

for (int i = 0; i < answer.size(); i++)

{

cout << answer[i] << " ";

}

cout << endl;

}

return 0;

}

Описание решения:

Для решения данной задачи необходимо было воспользоваться алгоритмом топологической сортировки, посредством поиcка в глубину. Чтобы применить данный алгоритм, необходимо было проверить граф на ацикличность с помощью алгоритма поиска в глубину. Это было реализовано функцией [latex]cyclic[/latex], которая проходила по всему графу в поиске цикла. Если цикл был найден, то функция меняла значение переменной [latex]cycle_st[/latex]. Далее, если цикл был найден, то программа выводить -1, иначе применяется алгоритм топологической сортировки, реализованный в двух функциях:

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

20	void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

30	void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

После выполнения этих функций был получен топологически отсортированный список вершин, но в обратном порядке. Поэтому разворачиваем его с помощью функции [latex]reverse[/latex] .

Засчитанное решение на e-olymp.com.

Код решения на ideone.com.

Related Images:

e-olymp 4003. Топологическая сортировка

26/03/2016 by Сплошнов Кирилл

Задача взята отсюда.

Условие

Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.

Входные данные

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]m[/latex] ([latex]1 \leq n \leq 10^5[/latex], [latex]1 \leq m \leq 10^5[/latex]) — количество вершин и рёбер в графе соответственно. Далее в [latex]m[/latex] строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Выходные данные

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести [latex]-1[/latex].

Решение

Для решения использовался алгоритм топологической сортировки методом поиска в глубину (подробнее в комментариях к коду). Функция bool dfs() (поиск в глубину) также проверяет, цикличен ли граф, т.к. по условию он может как содержать, так и не содержать циклы. Результат сортировки заносим в вектор result, потом выводим его элементы по порядку.

Тесты

№	Входные данные	Выходные данные
1	6 6 1 2 3 2 4 2 2 5 6 5 4 6	4 6 3 1 2 5
2	3 3 1 2 2 3 3 1	-1
3	4 4 1 4 4 3 3 2 4 2	1 4 3 2

Код

#include <iostream>
#include <vector>
#include <algorithm>
#define WHITE 0 //вершина не посещена
#define GREY 1 //вершина обрабатывается
#define BLACK 2 //вершина обработана
using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл
{
	state[v] = GREY; //отмечаем, что вершина в процессе обработки
	for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной
	{
		int dest = vertex[v].at(i);
		if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл
		{
			if (dfs(dest, vertex, state, result, size))
				return true;
		}
		else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл
		{
			return true;
		}
	}
    //если цикл не найден:
	state[v] = BLACK; //помечаем вершину как обработанную
	result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки
	return false;
}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)
{
	for (int i = 0; i < size; i++) //для каждой вершины графа
	{
		if (state[i] == WHITE) //если она еще не посещена
		{
			bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину
			if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)
			{
				result.clear();
				result.push_back(-1);
				return;
			}
		}
	}
	reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()
}

int main() 
{
	ios::sync_with_stdio(false); 
	int n, m;
	cin >> n >> m;
	vector<int> vertex[n]; //сам граф
	int state[n]; //массив состояний вершин
	vector<int> result;
	fill (state, state + n, WHITE); //изначально ни одна вершина не посещена
	for (int i = 0; i < n; i++)
	{
		int begin, end;
		cin >> begin >> end;
		vertex[begin-1].push_back(end-1);
	}
	topologicalSort(vertex, state, result, n); //сортируем граф
	for (int i = 0; i < result.size(); i++)
		cout << result.at(i) << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#define WHITE 0 //вершина не посещена

#define GREY 1 //вершина обрабатывается

#define BLACK 2 //вершина обработана

using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл

{

state[v] = GREY; //отмечаем, что вершина в процессе обработки

for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной

{

int dest = vertex[v].at(i);

if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл

{

if (dfs(dest, vertex, state, result, size))

return true;

}

else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл

{

return true;

}

//если цикл не найден:

state[v] = BLACK; //помечаем вершину как обработанную

result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки

return false;

}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)

{

for (int i = 0; i < size; i++) //для каждой вершины графа

{

if (state[i] == WHITE) //если она еще не посещена

{

bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину

if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)

{

result.clear();

result.push_back(-1);

return;

}

reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()

}

int main()

{

ios::sync_with_stdio(false);

int n, m;

cin >> n >> m;

vector<int> vertex[n]; //сам граф

int state[n]; //массив состояний вершин

vector<int> result;

fill (state, state + n, WHITE); //изначально ни одна вершина не посещена

for (int i = 0; i < n; i++)

{

int begin, end;

cin >> begin >> end;

vertex[begin-1].push_back(end-1);

}

topologicalSort(vertex, state, result, n); //сортируем граф

for (int i = 0; i < result.size(); i++)

cout << result.at(i) << " ";

return 0;

}

Ссылки

Код на ideaone.

Засчитанное решение на e-olymp.

Наглядное объяснение топологической сортировки здесь.

Related Images:

e-olimp 1667. Конденсация графа

29/03/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

Входные данные

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex] до [latex]N[/latex] — номера начала и конца ребра.

Выходные данные

В первой строке выведите число [latex]K[/latex] — количество компонент сильной связности в заданном графе. В следующей строке выведите [latex]N[/latex] чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Тесты:

6 7

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

Иллюстрация ко второму тесту:

Код программы:

#include <iostream>
#include <vector>
using namespace std;

vector <int> G[100010];
vector <int> Gt[100010]; // транспонированній граф
vector<bool> used;
vector<int> order, component;
int res[100010];
int n, m, num=1;

void dfs_1 (int u) {
 used[u]=1;
 for (int i=0; i<G[u].size(); i++) {
     if (used[G[u][i]]==0) {
         dfs_1(G[u][i]);
     }
 }
 order.push_back(u);
}

void dfs_2 (int u) {
  used[u]=1;
  component.push_back(u);
  for (int i=0; i<Gt[u].size(); i++) {
      if (used[Gt[u][i]]==0) {
          dfs_2 (Gt[u][i]);
      }
  }
}

int main() {
 ios::sync_with_stdio(false);
 cin >> n >> m;
 
 while (m--) {
     int a, b;
     cin >> a >> b;
     a--;
     b--;
     G[a].push_back(b);
     Gt[b].push_back(a);
 }
 
 used.assign (n, false);

 for (int i=0; i<n; i++) {
         if (used[i]==0) dfs_1(i);
 }
 
 used.assign (n, false);
 
 for (int i=0; i<n; i++) {
      int v=order[n-1-i];
      if (used[v]==0) {
          dfs_2 (v);
          for(auto I=component.begin(); I!=component.end(); I++)
              res[*I]=num;
          num++;
          component.clear();
      }
  }
  
  cout << num-1 << endl;
  for (int i=0; i<n-1; i++) cout << res[i] << " ";
  cout << res[n-1] << endl;
  return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector <int> G[100010];

vector <int> Gt[100010]; // транспонированній граф

vector<bool> used;

vector<int> order, component;

int res[100010];

int n, m, num=1;

void dfs_1 (int u) {

used[u]=1;

for (int i=0; i<G[u].size(); i++) {

if (used[G[u][i]]==0) {

dfs_1(G[u][i]);

}

order.push_back(u);

}

void dfs_2 (int u) {

used[u]=1;

component.push_back(u);

for (int i=0; i<Gt[u].size(); i++) {

if (used[Gt[u][i]]==0) {

dfs_2 (Gt[u][i]);

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

a--;

b--;

G[a].push_back(b);

Gt[b].push_back(a);

}

used.assign (n, false);

for (int i=0; i<n; i++) {

if (used[i]==0) dfs_1(i);

}

used.assign (n, false);

for (int i=0; i<n; i++) {

int v=order[n-1-i];

if (used[v]==0) {

dfs_2 (v);

for(auto I=component.begin(); I!=component.end(); I++)

res[*I]=num;

num++;

component.clear();

}

cout << num-1 << endl;

for (int i=0; i<n-1; i++) cout << res[i] << " ";

cout << res[n-1] << endl;

return 0;

}

Алгоритм решения

Прежде всего топологически сортируем граф [latex]G[/latex] (с помощью функции dfs_1), записывая результат в вектор order. В итоге первой вершиной этого вектора окажется некая вершина [latex]u[/latex], принадлежащая «корневой» компоненте сильной связности, то есть в которую не входит ни одно ребро в графе конденсаций.

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

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

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

Related Images:

e-olimp 553. Рекурсия

20/03/2015 by Бронфен-Бова Роман

Задача: Рекурсия

Решение

ссылка на ideone, засчитанное решение на e-olimp

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
using namespace std;

map<string,set<string>> G;
map<string,bool> used;
map<string,bool> rec;
vector<string> V;

void dfs(string cur, string aim){
   if(used[cur] || rec[aim]) return;
   used[cur] = 1;
   for(auto i = G[cur].begin(); i != G[cur].end(); i++){
      if(*i != aim){
         dfs(*i,aim);
      }else{
         rec[aim] = 1;
         return;
      }
   }
}

int main(){
   //input
   int n; cin >> n;
   for(int i = 0; i < n; i++){
      string curVert; cin >> curVert;
      V.push_back(curVert);
      int m; cin >> m;
      while(m--){
         string inp; cin >> inp;
         G[curVert].insert(inp);
      }
      if(i != n-1){
         string stars;
         cin >> stars;
      }
   }
   //work
   for(auto i : V){
      dfs(i, i);
      used.clear();
   }
   for(auto i : V){
      cout << i << (rec[i] ? ": YES" : ": NO") << endl;
   }
   return 0;
}

#include<iostream>

#include<vector>

#include<set>

#include<map>

#include<string>

using namespace std;

map<string,set<string>> G;

map<string,bool> used;

map<string,bool> rec;

vector<string> V;

void dfs(string cur, string aim){

if(used[cur] || rec[aim]) return;

used[cur] = 1;

for(auto i = G[cur].begin(); i != G[cur].end(); i++){

if(*i != aim){

dfs(*i,aim);

}else{

rec[aim] = 1;

return;

}

int main(){

//input

int n; cin >> n;

for(int i = 0; i < n; i++){

string curVert; cin >> curVert;

V.push_back(curVert);

int m; cin >> m;

while(m--){

string inp; cin >> inp;

G[curVert].insert(inp);

}

if(i != n-1){

string stars;

cin >> stars;

}

//work

for(auto i : V){

dfs(i, i);

used.clear();

}

for(auto i : V){

cout << i << (rec[i] ? ": YES" : ": NO") << endl;

}

return 0;

}

Идея решения

Можно заметить, что каждая процедура — это вершина ориентированного графа. Чтобы узнать, является ли процедура потенциально рекурсивной, нужно было запустить из неё поиск в глубину и узнать, сможем ли мы прийти к ней вновь.

Было решено использовать map<string,set<string>> как структуру для описания графа: каждая вершина — это строка и у каждой вершины есть множество вершин (строк), смежных с ней.
А еще задача имеет классификацию — поиск в глубину, что как бы намекает.