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

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

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

1.Задача A:

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

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

В первой строке входного файла заданы числа M и N через пробел - количество вершин и ребер в графе, соответственно (1 ≤ N ≤ 100, 0 ≤ M ≤ 10 000). Следующие M строк содержат по два числа ui и vi через пробел, каждая такая строка означает, что в графе существует ребро между вершинами ui и vi .

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

Выведите "YES", если граф является связным, и "NO" в противном случае.

Пример:

Ввод:

3 2

1 2

3 2

Вывод:

YES

Решение:

#include <iostream>
#include <vector>

using namespace std;

vector<bool> used(101, false);

void dfs(const vector<vector<int> >& gr, int from) {
    used[from] = true;
    for (size_t i = 0; i < gr[from].size(); ++i) {
        if (!used[gr[from][i]]) {
            dfs(gr, gr[from][i]);
        }
    }
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > graph(n+1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    int count = 0;
    for (size_t i = 1; i < graph.size(); ++i) {
        if (!used[i]) {
            ++count;
            dfs(graph, i);
        }
    }
    
    cout << count << "\n";
    for ()
    
    return 0;
}

2.Задача B:

Задан неориентированный граф с N вершинами и M ребрами (1 ≤ N ≤ 20 000, 0 ≤ M ≤ 200 000). В графе отсутствует петли и кратные ребра. Определите компонент связности заданного графа.

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

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

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

На первой строке выходного файла выведите число L - количество компонентов связности заданного графа. На следующей строке выведите N чисел из диапазона от 1 до L - номера компонент связности, которым принадлежат соответствующие вершины. Компоненты связности следует занумеровать от 1 до L произвольным образом.

Пример:

Ввод:

4 2

1 2

3 4

Вывод:

2

1 1 2 2

Решение:

#include <iostream>
#include <vector>

using namespace std;

vector<bool> used(20001, false);
vector<int> connectedComponent(20001);

void dfs(const vector<vector<int> >& gr, int from, int component) {
    used[from] = true;
    connectedComponent[from] = component;
    for (size_t i = 0; i < gr[from].size(); ++i) {
        if (!used[gr[from][i]]) {
            dfs(gr, gr[from][i], component);
        }
    }
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > graph(n+1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    int count = 0;
    for (size_t i = 1; i < graph.size(); ++i) {
        if (!used[i]) {
            ++count;
            dfs(graph, i, count);
        }
    }
    
    cout << count << "\n";
    for (size_t i = 1; i <= n; ++i) {
        cout << connectedComponent[i] << " ";
    }
        
    return 0;
}

3.Задача C:

Пошаговым обходом графа из вершины v назовем последовательность вершин u1, u2, ..., ur такую, что:

  • $$u_1 = u_r = v$$
  • Каждая вершина графа, достижимая из v , встречается в ней хотя бы один раз
  • Между любыми двумя соседними вершинами последовательности в графе существует ребро. Задан связный неориентированный граф и его вершина v. Выведите любой пошаговый обход этого графа.

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

В первой строке входного файла заданы числа N, M и v через пробел - количество вершин и ребер в графе и начальная вершина обхода (1 ≤ N ≤ 100, 0 ≤ M ≤ 10 000). Следующие M строк содержат по два числа ui и vi через пробел, каждая такая строчка означает, что в графе существует ребро между вершинами .

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

В первой строке входного файла выведите число r - количество вершин в найденном пошаговом обходе (1 ≤ r ≤ 10 000); гарантируется, что обход, удовлетворяющий этим ограничениям, существует). Во второй строке выведите сами числа $$u_1, u_2, ..., u_r$$ через пробел ui и vi.

Пример:

Ввод:

3 2 1

1 2

2 3

Вывод:

5

1 2 3 2 1

Решение:

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

vector<bool> used;
vector<vector<int> >gr;

vector<int>path;

void dfs(int cur) {
    used[cur] = true;
    for (auto& u : gr[cur]) {
        if (!used[u]) {
            path.push_back(u);
            dfs(u);
            path.push_back(cur);
        }
    }
}

int main() {
    int n, m, begin;
    cin >> n >> m >> begin;
    used.assign(n, false);
    gr.assign(n, vector<int>());
    
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        gr[a-1].push_back(b-1);
        gr[b-1].push_back(a-1);
    }
    
    path.push_back(begin-1);
    dfs(begin-1);
    
    cout << path.size() << "\n";
    for (auto& a : path) {
        cout << a+1 << " ";
    }
    
    return 0;
}