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:

Код Хаффмана

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 2267. Journey

03/06/2016 by Таран Таня

The army of Rzeczpospolita is moving from the city Kostroma to the village Domnino. Two hetmans, Stefan and Konstantin, lead the army.

Stefan procured the roadmap of Kostroma province, and every night he routes the army from one village to the other along some road. Konstantin bought the map of secret trails between villages in advance, and every day he leads the march along the one of such trails. Each hetman asks their guide Ivan Susanin for a route before each march.

The length of each road is indicated on Stefan’s map. So Stefan knows the minimal distance from each village to the Domnino village according to his map. Similarly Konstantin knows the minimal distance from each village to Domnino village along trails on his map.

Ivan Susanin does not want to be disclosed as a secret agent, so each time he chooses a road (for Stefan) or a trail (for Konstantin) so, that the minimal distance to the Domnino village according to the map owned by the asking hetman is strictly decreasing.

Help Ivan to ﬁnd the longest possible route to the Domnino village.

Input

The ﬁrst line contains three integer numbers [latex]n, s[/latex] and [latex]t[/latex] — number of villages in Kostroma province, and numbers of start and Domnino village [latex](2 \le n \le 1000; 1 \le s; t \le n)[/latex]. Villages are numbered from [latex]1[/latex] to [latex]n[/latex]. Start and Domnino villages are distinct.

Two blocks follow, the ﬁrst one describing Stefan’s map, and the second one describing Konstantin’s map.

The first line of each block contains an integer number [latex]m[/latex] — the number of roads/trails between villages [latex](n-1 \le m \le 100000)[/latex]. Each of the following [latex]m[/latex]lines contains three integer numbers [latex]a, b[/latex], and [latex]l[/latex] — describing the road/trail between villages [latex]a[/latex] and [latex]b[/latex] of length [latex]l[/latex] [latex](1 \le a, b \le n; 1 \le l \le 10^6)[/latex].

Rzeczpospolita army can move in any direction along a road or a trail. It’s guaranteed that one can travel from any village to any other using each of the maps. The army starts its movement in the evening from the village number and moves one road each night and one trail each day.

Output

Output the total length of the longest route that Ivan Susanin can arrange for Rzeczpospolita army before reaching the Domnino village (along the roads and trails). If Ivan Susanin can route the army forever without reaching the Domnino village, output the number «[latex]-1[/latex]».

Tests

№	Input	Output
1	5 1 5 5 1 2 2 1 4 2 2 3 1 3 4 1 5 3 1 4 1 2 2 2 4 2 2 3 1 2 5 2	-1
2	3 1 3 4 1 2 10 2 3 10 1 3 20 2 3 30 4 2 1 10 1 3 10 1 1 10 2 3 10	20

Algorithm

The problem has been resolved together with Sploshnov Kirill.

So, we are dealing with a rather cumbersome task for the graphs, therefore we analyze it consistently. To get started we define the data structure

struct Route {
    int color;
    unsigned int to; 
    unsigned int length;
};

struct Route {

int color;

unsigned int to;

unsigned int length;

};

because dealing with the routes and subsequently, we will have to color our edges. For convenience, we don’t think about two maps as about different graphs, and can establish one graph, where edges of each map are painted in a different color.
For example edges of first map color in RED, and the other in BLUE. Then select the first map is equivalent to passing by red edges, or blue otherwise. In this way, route, that we are looking for, should be based on the successively alternating colors of the edges.
Proceed directly to the solution.
From the condition is understandable, that each hetman knows the shortest path to the final village. This data will be needed for us too, so for each map (edges of the same color) use Dijkstra’s algorithm and find the shortest path from each vertex to the target. (Function void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color); ). We need absolutely standard Dijkstra’s algorithm with the only difference that the edges of the opposite color aren’t available. You can learn more about Dijkstra’s algorithm in the sources of information listed at the end of the article.
Continue analyzing the condition, we understand, that we can’t pass over the edges so, that the shortest distance to the final vertex increased. This will help us to simplify the graph, and significantly reduce the number of possible variants of passage, namely, any bidirectional edge will be either removed completely or strictly directed. Then, passing on to the edges of the same color in each map, if it doesn’t satisfy the specified condition coloring it as DELETED. (Function void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color); ).
Now we can get started with the search for the longest route. There are two options: either there is the longest path, or we can walk along the edges infinitely, if it does not contradict the statement of the problem, that is, in the combined of two maps graph there is a cycle. So we organize checks on acyclic. Now we have the right to pass along the edges only alternating colors at each step. In order to find a cycle, we use vertex coloring, and will explore the graph until we try to treat already colored vertex or not conclude that it is acyclic. (Function bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color); ). This algorithm can be obtained after detailed acquaintance with the usual cycle searching algorithm (reference to the source is located at the end of the article). If we find any loop in this graph, then our job is over and we should just output «[latex]-1[/latex]».
Otherwise, make sure that the graph is acyclic, we are looking for the longest route. As our graph has been simplified and has no cycles, and all edges are directed, then the task of finding this way becomes computationally simple. For this declaring an array of longest distance dynamically, along the way memorizing the already calculated values, sequentially find the maximum length of the route until we arrive at the finish village. (Function int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) ). This will be the answer to the task.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <vector>
#include <iostream>
#include <algorithm>
#define DELETED -1
#define WHITE 0
#define GREY 1
#define BLACK 2
#define RED 3
#define BLUE 4
#define MAX_INT 2147483647
using namespace std;
 
//  The structure, describing the roads/trails 
struct Route {
    int color;
    unsigned int to; 
    unsigned int length;
    //  Constructor by destination, length and color of edge
    Route(unsigned int to, unsigned int length, int color) {
        this->to = to;
        this->color = color;
        this->length = length;
    }
};
 
/*  
    Function implements ordinary Dijkstra's algorithm (for all edges of the same color)
    As a result, an array of distances filled with the minimum distance to each vertex
*/
void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {
    int vertexWithMinDist = -1;
    bool* passed = new bool[quantityOfAllVertices];
    fill(passed, passed + quantityOfAllVertices, false);
    fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);
    distancesInColoredGraph[finishVertex] = 0;
    for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {
        vertexWithMinDist = -1;
        for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {
            if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {
                vertexWithMinDist = indexOfVertex;
            }
        }
        passed[vertexWithMinDist] = true;
        for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {
            if (graph[vertexWithMinDist][adjacentVertex].color == color 
                && graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {
                distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];
            }
        }
    }
}
 
//  Function indicates the edges we don't need as deleted (because we can't pass them)
void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {
    //  Note as DELETED routes in which the minimum distance to finish vertex increases, cause we can't walk them on the strength of problem's condition
    for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {
        for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {
            if (graph[indexOfCurrentVertex][adjacentVertex].color == color 
                && distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {
                graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;
            }
        }
    }
}
 
//  Function determines whether you can go in cycle by the edges of alternating colors 
bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {
    bool answer = false;
    //  Note processing vertex
    if (color == RED) {
        passedInRedGraph[currentVertex] = GREY;
    } else {
        passedInBlueGraph[currentVertex] = GREY;
    }
    /*
        Implement ordinary checking on cycle, by coloring graph
        Treat until we don't determine it is acyclic or try to color vertex that is already colored
        We should take into account the fact, that each time we alternate the color of the edges
    */
    for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {
        if (graph[currentVertex][adjacentVertex].color == color) {
            if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY 
                || color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {
                answer = true;
            }
            if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
                if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {
                    answer = true;
                }
            } else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
                if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {
                    answer = true;
                }
            }
        }
    }
    //  Note processed vertex
    if (color == RED) {
        passedInRedGraph[currentVertex] = BLACK;
    } else {
        passedInBlueGraph[currentVertex] = BLACK;
    }
    return answer;
}
 
//  Function determines whether there is a suitable cycle in the graph
bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {
    int* passedInRedGraph = new int[quantityOfAllVertices];
    int* passedInBlueGraph = new int[quantityOfAllVertices];
    fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);
    fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);
    return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);
}
 
//  Function determines the longest path in the graph by the edges of alternating colors, by finding and memorizing the maximum path to each of the vertices
int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {
    //  Return the length of the path from the current vertex, if it's found already
    if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {
        return maxDistancesInRedGraph[currentVertex];
    }
    if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {
        return maxDistancesInBlueGraph[currentVertex];
    }
    int maxDistance = -1;   //  Initially, we consider the longest path by any negative number
    for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {
        /*
            Recursively find the longest path to the finish vertex
            We should take into account the fact, that each time we alternate the color of the edges
        */
        if (graph[currentVertex][adjacentVertex].color == color) {
            int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to, 
                color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;
            maxDistance = max(maxDistance, currentMaxDistance);
        }
    }
    //  Remember the results received in the process of bypassing for later use
    if (color == RED) {
        maxDistancesInRedGraph[currentVertex] = maxDistance;
    } else {
        maxDistancesInBlueGraph[currentVertex] = maxDistance;
    }
    return maxDistance;
}
 
//  Function returns the longest path in the graph from the start vertex to the finish
int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {
    int* maxDistancesInRedGraph = new int[quantityOfAllVertices];
    int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];
    fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);
    fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);
    maxDistancesInRedGraph[finishVertex] = 0;
    maxDistancesInBlueGraph[finishVertex] = 0;
    return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);
}
 
int main() {
    ios::sync_with_stdio(false);
    unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;
    cin >> quantityOfAllVertices >> startVertex >> finishVertex;
    startVertex--; finishVertex--;  //  Shift numbering
    vector<Route>* graph = new vector<Route>[quantityOfAllVertices];    // Stores graph as array of routes for each vertex
    cin >> quantityOfVertices;
    while (quantityOfVertices--) {
        cin >> from >> to >> length;
        from--; to--;   //  Shift numbering
        if (from != to) {   //  Don't read cycles
            // Initially, all roads are bidirectional, add symmetrically
            graph[from].push_back(Route(to, length, RED));
            graph[to].push_back(Route(from, length, RED));
        }
    }
    cin >> quantityOfVertices;
    while (quantityOfVertices--) {
        cin >> from >> to >> length;
        from--; to--; 
        if (from != to) {
            graph[from].push_back(Route(to, length, BLUE));
            graph[to].push_back(Route(from, length, BLUE));
        }
    }
    int* distancesInRedGraph = new int[quantityOfAllVertices];  //  Shortest distances from each vertex to the final by red edges
    int* distancesInBlueGraph = new int[quantityOfAllVertices]; //  Shortest distances from each vertex to the final by blue edges
    djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED);     //  Find and remember the shortest path by the red edges
    djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE);   //  Find and remember the shortest path by the blue edges
    simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED);   //  Note red edges which we can't pass, so that later they don't take into account
    simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); //  Note blue edges which we can't pass, so that later they don't take into account
    cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;
    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

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

#include <vector>

#include <iostream>

#include <algorithm>

#define DELETED -1

#define WHITE 0

#define GREY 1

#define BLACK 2

#define RED 3

#define BLUE 4

#define MAX_INT 2147483647

using namespace std;

// The structure, describing the roads/trails

struct Route {

int color;

unsigned int to;

unsigned int length;

// Constructor by destination, length and color of edge

Route(unsigned int to, unsigned int length, int color) {

this->to = to;

this->color = color;

this->length = length;

}

};

Function implements ordinary Dijkstra's algorithm (for all edges of the same color)

As a result, an array of distances filled with the minimum distance to each vertex

void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {

int vertexWithMinDist = -1;

bool* passed = new bool[quantityOfAllVertices];

fill(passed, passed + quantityOfAllVertices, false);

fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);

distancesInColoredGraph[finishVertex] = 0;

for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {

vertexWithMinDist = -1;

for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {

if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {

vertexWithMinDist = indexOfVertex;

}

passed[vertexWithMinDist] = true;

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {

if (graph[vertexWithMinDist][adjacentVertex].color == color

&& graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {

distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];

}

// Function indicates the edges we don't need as deleted (because we can't pass them)

void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {

// Note as DELETED routes in which the minimum distance to finish vertex increases, cause we can't walk them on the strength of problem's condition

for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {

if (graph[indexOfCurrentVertex][adjacentVertex].color == color

&& distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {

graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;

}

// Function determines whether you can go in cycle by the edges of alternating colors

bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {

bool answer = false;

// Note processing vertex

if (color == RED) {

passedInRedGraph[currentVertex] = GREY;

} else {

passedInBlueGraph[currentVertex] = GREY;

}

Implement ordinary checking on cycle, by coloring graph

Treat until we don't determine it is acyclic or try to color vertex that is already colored

We should take into account the fact, that each time we alternate the color of the edges

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {

if (graph[currentVertex][adjacentVertex].color == color) {

if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY

|| color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {

answer = true;

}

if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {

if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {

answer = true;

}

} else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {

if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {

answer = true;

}

// Note processed vertex

if (color == RED) {

passedInRedGraph[currentVertex] = BLACK;

} else {

passedInBlueGraph[currentVertex] = BLACK;

}

return answer;

}

// Function determines whether there is a suitable cycle in the graph

bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {

int* passedInRedGraph = new int[quantityOfAllVertices];

int* passedInBlueGraph = new int[quantityOfAllVertices];

fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);

fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);

return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);

}

// Function determines the longest path in the graph by the edges of alternating colors, by finding and memorizing the maximum path to each of the vertices

int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {

// Return the length of the path from the current vertex, if it's found already

if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {

return maxDistancesInRedGraph[currentVertex];

}

if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {

return maxDistancesInBlueGraph[currentVertex];

}

int maxDistance = -1; // Initially, we consider the longest path by any negative number

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {

Recursively find the longest path to the finish vertex

We should take into account the fact, that each time we alternate the color of the edges

if (graph[currentVertex][adjacentVertex].color == color) {

int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to,

color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;

maxDistance = max(maxDistance, currentMaxDistance);

}

// Remember the results received in the process of bypassing for later use

if (color == RED) {

maxDistancesInRedGraph[currentVertex] = maxDistance;

} else {

maxDistancesInBlueGraph[currentVertex] = maxDistance;

}

return maxDistance;

}

// Function returns the longest path in the graph from the start vertex to the finish

int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {

int* maxDistancesInRedGraph = new int[quantityOfAllVertices];

int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];

fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);

fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);

maxDistancesInRedGraph[finishVertex] = 0;

maxDistancesInBlueGraph[finishVertex] = 0;

return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);

}

int main() {

ios::sync_with_stdio(false);

unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;

cin >> quantityOfAllVertices >> startVertex >> finishVertex;

startVertex--; finishVertex--; // Shift numbering

vector<Route>* graph = new vector<Route>[quantityOfAllVertices]; // Stores graph as array of routes for each vertex

cin >> quantityOfVertices;

while (quantityOfVertices--) {

cin >> from >> to >> length;

from--; to--; // Shift numbering

if (from != to) { // Don't read cycles

// Initially, all roads are bidirectional, add symmetrically

graph[from].push_back(Route(to, length, RED));

graph[to].push_back(Route(from, length, RED));

}

cin >> quantityOfVertices;

while (quantityOfVertices--) {

cin >> from >> to >> length;

from--; to--;

if (from != to) {

graph[from].push_back(Route(to, length, BLUE));

graph[to].push_back(Route(from, length, BLUE));

}

int* distancesInRedGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by red edges

int* distancesInBlueGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by blue edges

djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED); // Find and remember the shortest path by the red edges

djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE); // Find and remember the shortest path by the blue edges

simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED); // Note red edges which we can't pass, so that later they don't take into account

simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); // Note blue edges which we can't pass, so that later they don't take into account

cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;

return 0;

}

Related Images:

e-olimp 122. Горные маршруты

02/04/2015 by Вустянюк Ігор Дмитрович

Задача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?
Ссылка на задачу

Пояснение к решению

Поиск путей представляет из себя модифицированный обход в глубину. Вместо массива «глобально посещённых» вершин, в которые уже нельзя возвращаться при обходе, я использую массив «локально посещённых» вершин. Это позволяет использовать одну и ту же вершину в разных, в том числе очень длинных и извращённых путях (в стандартном варианте ищется кратчайший путь, а нам нужны все: в том числе длинные и извращённые).

Кроме того, добавлен параметр depth — длина рассматриваемого в данный момент пути (или глубина текущего рекуррентного вызова, если угодно). Этот параметр изначально имеет значение 0 и при каждом вызове сравнивается с максимально допустимым значением. Перед рекуррентным вызовом мы увеличиваем значение depth, ведь длина нового пути будет на 1 больше. После вызова, т.е. возвращаясь на предыдущий уровень рекурсии, мы уменьшаем длину пути (ведь мы «отбросили» последнюю вершину, т.е. длина пути уменьшилась на 1).

Алгоритм работает примерно так: сначала посещаем начальную вершину и помечаем её как локально посещённую. Если она — искомая, увеличиваем количество найденных путей на 1 и алгоритм завершает свою работу (путей без циклов, содержащих более одной вершины, в этом случае быть не может). Если же начальная вершина не совпадает с целевой, то для всех вершин, в которые можно попасть из неё, применяем рекуррентно тот же алгоритм. Если таких вершин нет, алгоритм завершается, возвращая 0 (нет ни одного пути из начальной вершины в конечную). Если же такие вершины имеются, то увеличиваем параметр «глубина» и вызываем для них рекуррентно наш алгоритм. После выхода из рекурсии, возвращаем параметр «глубина» к последнему его значению (тем, что было перед вызовом) и, чтобы мы могли использовать данную вершину в других путях помечаем её как «локально свободную».

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

Решение на С++

#include <stdio.h>
#include <vector>
#include <stdlib.h>
using namespace std;

struct Graph {
	vector< vector<int> > AdjList;
	int Size;
	
	Graph(int n) {
		vector<int> List;
		for (int k = 0; k < n; k++)
			AdjList.push_back(List);
		Size = n;
	}

	void add_vertex() {					// вершина == целое число == номер этой вершины в списке вершин
		Size++;
		vector<int> List;
		AdjList.push_back(List);
	}
	
	void add_edge(int u, int v) {		// u и v уже должны быть в списке вершин
		AdjList[u].push_back(v);
	}

	int simple_paths(int start, int end, int max_depth) {
		bool* on_path = (bool*) calloc(Size, sizeof(bool));
		int cur_depth = 0;
		int count = 0;
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count;
	}
	
	void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {
		if (cur_depth <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count++;
			else
				for (int k = 0; k < AdjList[start].size(); k++) {
					int v = AdjList[start][k];
					if (!on_path[v]) {
						cur_depth++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth--;
					}
				}
		}
	}
	
};


int main() {
	int n, k, a, b, d, tmp1, tmp2;
	scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);
	Graph G(n);
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &tmp1, &tmp2);
		G.add_edge(tmp1 - 1, tmp2 - 1);
	}
	printf("%d\n", G.simple_paths(a-1, b-1, d));
	return 0;
}

#include <stdio.h>

#include <vector>

#include <stdlib.h>

using namespace std;

struct Graph {

vector< vector<int> > AdjList;

int Size;

Graph(int n) {

vector<int> List;

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

AdjList.push_back(List);

Size = n;

}

void add_vertex() { // вершина == целое число == номер этой вершины в списке вершин

Size++;

vector<int> List;

AdjList.push_back(List);

}

void add_edge(int u, int v) { // u и v уже должны быть в списке вершин

AdjList[u].push_back(v);

}

int simple_paths(int start, int end, int max_depth) {

bool* on_path = (bool*) calloc(Size, sizeof(bool));

int cur_depth = 0;

int count = 0;

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count;

}

void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {

if (cur_depth <= max_depth) {

on_path[start] = true;

if (start == end)

count++;

else

for (int k = 0; k < AdjList[start].size(); k++) {

int v = AdjList[start][k];

if (!on_path[v]) {

cur_depth++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth--;

}

};

int main() {

int n, k, a, b, d, tmp1, tmp2;

scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);

Graph G(n);

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

scanf("%d %d", &tmp1, &tmp2);

G.add_edge(tmp1 - 1, tmp2 - 1);

}

printf("%d\n", G.simple_paths(a-1, b-1, d));

return 0;

}

Решение на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class myInt {
	int v;
	public myInt(int a) {
		this.v = a;
	}
}

class Graph {
	Vector<Vector<Integer>> AdjList;

	public Graph(int n) {
		AdjList = new Vector<Vector<Integer>>(n);
		for (int k = 0; k < n; k++)
			AdjList.add(new Vector<Integer>());
	}
	
	public void add_vertex() {
		AdjList.add(new Vector<Integer>());
	}
	
	public void add_edge(int u, int v) {
		AdjList.elementAt(u).add(v);
	}
	
	public int simple_paths(int start, int end, int max_depth) {
		boolean[] on_path = new boolean[AdjList.size()];
		myInt cur_depth = new myInt(0);
		myInt count = new myInt(0);
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count.v;
	}
	
	public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {
		if (cur_depth.v <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count.v++;
			else
				for (int k = 0; k < AdjList.elementAt(start).size(); k++) {
					int v = AdjList.elementAt(start).elementAt(k);
					if (!on_path[v]) {
						cur_depth.v++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth.v--;
					}
				}
		}
	}
}

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();
		int tmp1, tmp2;
		Graph G = new Graph(n);
		for (int i = 0; i < k; i++) {
			tmp1 = in.nextInt();
			tmp2 = in.nextInt();
			G.add_edge(tmp1 - 1, tmp2 - 1);
		}
		System.out.println(G.simple_paths(a-1, b-1, d));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class myInt {

int v;

public myInt(int a) {

this.v = a;

}

class Graph {

Vector<Vector<Integer>> AdjList;

public Graph(int n) {

AdjList = new Vector<Vector<Integer>>(n);

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

AdjList.add(new Vector<Integer>());

}

public void add_vertex() {

AdjList.add(new Vector<Integer>());

}

public void add_edge(int u, int v) {

AdjList.elementAt(u).add(v);

}

public int simple_paths(int start, int end, int max_depth) {

boolean[] on_path = new boolean[AdjList.size()];

myInt cur_depth = new myInt(0);

myInt count = new myInt(0);

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count.v;

}

public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {

if (cur_depth.v <= max_depth) {

on_path[start] = true;

if (start == end)

count.v++;

else

for (int k = 0; k < AdjList.elementAt(start).size(); k++) {

int v = AdjList.elementAt(start).elementAt(k);

if (!on_path[v]) {

cur_depth.v++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth.v--;

}

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), k = in.nextInt();

int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();

int tmp1, tmp2;

Graph G = new Graph(n);

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

tmp1 = in.nextInt();

tmp2 = in.nextInt();

G.add_edge(tmp1 - 1, tmp2 - 1);

}

System.out.println(G.simple_paths(a-1, b-1, d));

}

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 4004. Есть ли цикл?

22/03/2015 by Карташов Денис Геннадійович

Задача:

Дан ориентированный граф. Требуется определить, есть ли в нём цикл.

Технические условия:

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

В первой строке вводится натуральное число [latex]N ( N \leq 50)[/latex] — количество вершин. Далее в [latex]N[/latex] строках следуют по [latex]N[/latex] чисел, каждое из которых — «0» или «1«. [latex]j [/latex] -е число в [latex]i[/latex] -й строке равно «1» тогда и только тогда, когда существует ребро, идущее из [latex]i[/latex] -й вершины в [latex]j[/latex]-ю. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите «0«, если в заданном графе цикла нет, и «1«, если он есть.

Результат на С++

Результат на Java

Код на С++:

#include <iostream>
using namespace std;

int ** a; // Матрица смежности будет записана именно сюда.
int n = 51; // Число вершин. 
int * was;// Массив цвета вершины.

bool dfs(int key){
  //"Красим" вершину в серый цвет (указываем, что мы в нее вошли).
  was[key] = 1;
  //Проходим все связанные с текущей вершиной.
  for(int i = 0; i < n; i++){
  //Если значение элемента строки матрицы (по условию, нам дана матрица смежности) отлично от "0", то:
      if(a[key][i]){
          //если вершина "белая" (т. е. мы в неё еще не заходили)- 
          //запускаем рекурсивный вызов DFS от этой вершины.
          if(was[i] == 0){if(dfs(i)) return true;}
          //если вершина "серая" (мы её уже навещали, но не возвращались из ее потомков)-  
          //мы нашли цикл, следовательно поиск можно завершить.
          else if(was[i] == 1){ return true;}
      }
  }
  //Если ни один из if - ов не сработал, то "красим" вершину в черный цвет (отмечаем, как пройденную)
  was[key] = 2;
 //и возвращаем результат поиска (мы ничего не нашли).
  return false;
}
int main() {
  cin >> n;
  a = new int *[n];
  was = new int [n];
  for(int i = 0; i < n; i++){
      a[i] = new int [n];
      was[i] = 0;
      for(int j = 0; j < n; j++){
          cin >> a[i][j];
      }
  }
  for(int i = 0; i < n; i++){
      //Проверяем поиском каждую вершину. Если поиск оказался успешным - выводим "1". 
      //Проверка цвета сделана ради ускорения процесса, иначе в поиске пришлось бы проходить весь 
      //цикл, даже если вершина покрашена в черный цвет.
      if(!was[i]&&dfs(i)) {cout << "1\n"; return 0;}
  }
  //Если if ни разу не сработал - выводим "0".
  cout << "0\n";
  return 0;
}

#include <iostream>

using namespace std;

int ** a; // Матрица смежности будет записана именно сюда.

int n = 51; // Число вершин.

int * was;// Массив цвета вершины.

bool dfs(int key){

//"Красим" вершину в серый цвет (указываем, что мы в нее вошли).

was[key] = 1;

//Проходим все связанные с текущей вершиной.

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

//Если значение элемента строки матрицы (по условию, нам дана матрица смежности) отлично от "0", то:

if(a[key][i]){

//если вершина "белая" (т. е. мы в неё еще не заходили)-

//запускаем рекурсивный вызов DFS от этой вершины.

if(was[i] == 0){if(dfs(i)) return true;}

//если вершина "серая" (мы её уже навещали, но не возвращались из ее потомков)-

//мы нашли цикл, следовательно поиск можно завершить.

else if(was[i] == 1){ return true;}

}

//Если ни один из if - ов не сработал, то "красим" вершину в черный цвет (отмечаем, как пройденную)

was[key] = 2;

//и возвращаем результат поиска (мы ничего не нашли).

return false;

}

int main() {

cin >> n;

a = new int *[n];

was = new int [n];

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

a[i] = new int [n];

was[i] = 0;

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

cin >> a[i][j];

}

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

//Проверяем поиском каждую вершину. Если поиск оказался успешным - выводим "1".

//Проверка цвета сделана ради ускорения процесса, иначе в поиске пришлось бы проходить весь

//цикл, даже если вершина покрашена в черный цвет.

if(!was[i]&&dfs(i)) {cout << "1\n"; return 0;}

}

//Если if ни разу не сработал - выводим "0".

cout << "0\n";

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Graphdfs
{
	private int[][] matrix; // Матрица смежности будет записана именно сюда.
	private int n; // Число вершин. 
	private int[] was;// Массив цвета вершины.
	public Graphdfs(){}
	public Graphdfs(int n)
	{
		this.n = n;
		matrix = new int [n][n];
		was = new int [n];
	}
	public void setMatrix(Scanner in)
	{
		for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			matrix[i][j] = in.nextInt();
	}
	public void showMatrix()
	{
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				System.out.print(matrix[i][j]);
				if(j < n - 1) System.out.print(" ");
				else System.out.println();
			}
		}
	}
 	public boolean dfs(int key)
 	{
		was[key] = 1;
		for(int i = 0; i < n; i++)
		{
			if(matrix[key][i] != 0)
			{
				if(was[i] == 0){
					if(dfs(i)) return true;
				}
				else if(was[i] == 1){
					return true;
				}
			}
		}
		was[key] = 2;
		return false;
	}
	public int[] getWas(){
		return was;
	}
}

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//System.out.println("ok1");
		Scanner in = new Scanner(System.in);
		//System.out.println("ok2");
		int n = in.nextInt();
		//System.out.println("ok3");
		Graphdfs Graph = new Graphdfs(n);
		//System.out.println("ok4");
		Graph.setMatrix(in);
		//System.out.println("ok5");
		//Graph.showMatrix();
		for(int i = 0; i < n; i++){
			if(Graph.getWas()[i] == 0 &&Graph.dfs(i) == true) {System.out.println(1); System.exit(0);}
		}
		System.out.println(0);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Graphdfs

{

private int[][] matrix; // Матрица смежности будет записана именно сюда.

private int n; // Число вершин.

private int[] was;// Массив цвета вершины.

public Graphdfs(){}

public Graphdfs(int n)

{

this.n = n;

matrix = new int [n][n];

was = new int [n];

}

public void setMatrix(Scanner in)

{

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

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

matrix[i][j] = in.nextInt();

}

public void showMatrix()

{

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

{

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

{

System.out.print(matrix[i][j]);

if(j < n - 1) System.out.print(" ");

else System.out.println();

}

public boolean dfs(int key)

{

was[key] = 1;

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

{

if(matrix[key][i] != 0)

{

if(was[i] == 0){

if(dfs(i)) return true;

}

else if(was[i] == 1){

return true;

}

was[key] = 2;

return false;

}

public int[] getWas(){

return was;

}

public class Main

{

public static void main (String[] args) throws java.lang.Exception

{

//System.out.println("ok1");

Scanner in = new Scanner(System.in);

//System.out.println("ok2");

int n = in.nextInt();

//System.out.println("ok3");

Graphdfs Graph = new Graphdfs(n);

//System.out.println("ok4");

Graph.setMatrix(in);

//System.out.println("ok5");

//Graph.showMatrix();

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

if(Graph.getWas()[i] == 0 &&Graph.dfs(i) == true) {System.out.println(1); System.exit(0);}

}

System.out.println(0);

}

Пояснение:

Циклом в графе называется цепь, в которой первая и последняя вершина совпадает. Значит, если проходя по вершинам графа в лексикографическом порядке, в какой — то момент я попаду в вершину в которую вошел, но еще не вышел, то это будет означать, что я нашёл цикл.

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

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

Задача

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

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

Тесты

№

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

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

Решение

Ссылки

Related Images:

Related Images:

Задача

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

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

Тесты

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

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

Ссылки

Related Images:

Задача

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

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

Тест

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

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

Ссылки

Related Images:

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

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

Related Images:

Input

Output

Tests

Algorithm

Code

Links

Related Images:

Пояснение к решению

Related Images:

Related Images:

Задача:

Технические условия:

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

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

Код на С++:

Код на Java:

Пояснение:

Related Images:

Решение

Идея решения

Related Images: