ТГиК-2019-Семинар-25.11.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Задачи на тему: "Графы"

1.Задача D:

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

Формат ввода:

В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N ≤ 100 000, M ≤ 100 000) — количество вершин и рёбер в графе соответственно. Далее в M строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Формат вывода:

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

Пример:

Ввод:

2 2

1 2

2 1

Вывод:

YES

1 2

Решение:

#include <iostream>
#include <vector>

using namespace std;
vector<vector<int> > gr;
vector<int> parents;
vector<int> used;

int cycle_begin;
int cycle_end;

bool cycle = false;

bool dfs(int from) {
    used[from] = 1;
    for (const auto& to : gr[from]) {
        if (used[to] == 0) {
            parents[to] = from;
            if (dfs(to)) return true;
        } else if (used[to] == 1) {
            cycle_begin = to;
            cycle_end = from;
            cycle = true;
            return true;
        }
    }
    used[from] = 2;
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    gr.resize(n+1);
    parents.resize(n+1);
    used.assign(n+1, 0);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        gr[a].push_back(b);
    }
    
    for (int i = 0; i < gr.size(); ++i) {
        if (used[i] == 0 && dfs(i)) {
            break;
        }
    }
    
    if (!cycle) {
        cout << "NO";
    } else {
        cout << "YES\n";
        int cur = cycle_end;
        vector<int> path;
        while (cur != cycle_begin) {
            path.push_back(cur);
            cur = parents[cur];
        }
        path.push_back(cur);
        for (auto it = path.rbegin(); it != path.rend(); ++it) {
            cout << *it << " ";
        }
    }
    
    return 0;
}

2.Задача G:

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

Формат ввода:

В первой строке задано n — количество вершин в дереве (1 ≤ n ≤ 100). В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, . . ., n. Вершина 1 является корнем дерева.

Формат вывода:

В первой строке выведите максимальное расстояние от корня до остальных вершин дерева. Во второй строке выведите, сколько вершин дерева находятся от корня на таком расстоянии. В третьей строке выведите номера этих вершин через пробел в порядке возрастания.

Пример:

Ввод:

3

1

1

Вывод:

1

2

2 3

Решение:

#include <algorithm>
#include <queue>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    vector<vector<int> > gr(n+1);
    for (int i = 2; i <= n; ++i) {
        int a;
        cin >> a;
        gr[a].push_back(i);
    }
    
    vector<int> nodes;
    queue<int> q;
    q.push(1);
    int depth = -1;
    while (!q.empty()) {
        int m = q.size();
        depth += 1;
        nodes.clear();
        for (int i = 0; i < m; ++i) {
            int u = q.front();
            nodes.push_back(u);
            q.pop();
            for (const auto& v : gr[u]) {
                q.push(v);
            }
        }
    }
    
    sort(nodes.begin(), nodes.end());
    
    cout << depth << "\n" << nodes.size() << "\n";
    
    for (const auto& u : nodes) {
        cout << u << " ";
    }
    return 0;
}

3.Задача E:

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

Формат ввода:

В первой строке входного файла даны два натуральных числа N и M (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 100 000) — количество вершин и рёбер в графе соответственно. Далее в M строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Формат вывода:

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

Пример:

Ввод:

6 6

1 2

3 2

4 2

2 5

6 5

4 6

Вывод:

4 6 3 1 2 5

Решение:

#include <iostream>
#include <vector>

using namespace std;

vector<int> used(1e+5 + 1, 0);
vector<int> topSort;

bool haveCycle = false;

void dfs(const vector<vector<int> >& gr, int from) {
    used[from] = 1;
    for (size_t i = 0; i < gr[from].size(); ++i) {
        int to = gr[from][i];
        if (used[to] == 0) {
            dfs(gr, to);
        } else if (used[to] == 1) {
            haveCycle = true;
        }
    }
    topSort.push_back(from);
    used[from] = 2;
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > gr(n+1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        gr[a].push_back(b);
    }
    
    for (size_t i = 1; i < gr.size(); ++i) {
        if (used[i] != 2) {
            dfs(gr,i);
        }
    }
    
    if (haveCycle) {
        cout << -1;
    } else {
        for (auto it = topSort.rbegin(); it != topSort.rend(); ++it) {
            cout << *it << " ";
        }
    }
    
    return 0;
}