Веселые Ребята

@85959594 · Регистрация: 26.06.2021

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

Веселые ребята решили организовать сборы для программистов. Первое, что им нужно было сделать, так это составить задачи для отбора. Однако составлять задачи в одиночку не интересно, поэтому каждый из n составителей мог открыть чат с несколькими другими составителями, а мог и не открывать чатов. Мессенджер составителей работает так, что если составитель А открыл чат с составителем Б, то и у Б он откроется автоматически. Известно между какими составителями уже открыты чаты. Разузнайте, какое минимальное количество чатов нужно открыть дополнительно, чтобы любой составитель мог передать сообщение любому другому посредством открытых чатов (составители могут пересылать сообщения из чата в чат).

Входные данные:
В первой строке входных данных дается два числа разделенных пробелом n и m (1≤n,m≤100) - количество составителей и количество открытых чатов между ними. В следующих m строках дается по два числа x,y (1≤x,y≤100) - номера составителей между которыми открыт чат.

Выходные данные:
Выведите минимальное количество чатов которое нужно открыть, чтобы можно было переслать сообщение посредством открытых чатов

Пример 1:
Входные данные:
5 2
1 2
3 4
Выходные данные:
2

Пример 2:
Входные данные:
5 1
1 2
Выходные данные:
3

Пример 3:
Входные данные:
5 4
1 2
2 3
3 4
4 5
Выходные данные:
0

@LegionK · 30.06.2021, 15:14

Попробуйте построить граф, вершины которого - составители, а ребра - чаты. Тогда ответом будет количество компонент связности этого графа. Этот алгоритм можно найти в интернете, например на emaxx.

@85959594 · 30.06.2021, 21:25 **[ТС]**

Сообщение от LegionK

Попробуйте построить граф, вершины которого - составители, а ребра - чаты. Тогда ответом будет количество компонент связности этого графа. Этот алгоритм можно найти в интернете, например на emaxx.

можете скинуть ссылку, не смог найти

@TheCalligrapher · 30.06.2021, 22:21

Сообщение от LegionK

Тогда ответом будет количество компонент связности этого графа.

Ответом будет количество компонент связности этого графа минус 1.

@LegionK · 30.06.2021, 22:24

C++

#include <iostream>
#include <vector>
 
using namespace std;
 
int n,m;
vector<vector<int>>v;
 
int cnt = 0;
vector<int>used;
 
void dfs(int x){
 
    used[x] = 1;
 
    for(int i = 0;i<v[x].size();++i){
 
        int t = v[x][i];
 
        if(!used[t])dfs(t);
 
    }
 
}
 
 
int main()
{
    cin >> n >> m;
 
    v.resize(n); used.resize(n);
 
    for(int i = 0;i<m;++i){
 
        int a,b;
        cin >> a >> b;
 
        --a; --b;
 
        v[a].push_back(b);
        v[b].push_back(a);
 
    }
 
    for(int i = 0;i<n;++i){
 
        if(!used[i]){
 
            ++cnt;
 
            dfs(i);
        }
 
    }
 
    cout << cnt-1;
 
    return 0;
}

Добавлено через 12 секунд
TheCalligrapher, согласен.

@85959594 0 / 0 / 0 Регистрация: 26.06.2021 Сообщений: 8
		1
	Веселые Ребята 29.06.2021, 11:34. Показов 1532. Ответов 4 Метки нет (Все метки) Веселые ребята решили организовать сборы для программистов. Первое, что им нужно было сделать, так это составить задачи для отбора. Однако составлять задачи в одиночку не интересно, поэтому каждый из n составителей мог открыть чат с несколькими другими составителями, а мог и не открывать чатов. Мессенджер составителей работает так, что если составитель А открыл чат с составителем Б, то и у Б он откроется автоматически. Известно между какими составителями уже открыты чаты. Разузнайте, какое минимальное количество чатов нужно открыть дополнительно, чтобы любой составитель мог передать сообщение любому другому посредством открытых чатов (составители могут пересылать сообщения из чата в чат). Входные данные: В первой строке входных данных дается два числа разделенных пробелом n и m (1≤n,m≤100) - количество составителей и количество открытых чатов между ними. В следующих m строках дается по два числа x,y (1≤x,y≤100) - номера составителей между которыми открыт чат. Выходные данные: Выведите минимальное количество чатов которое нужно открыть, чтобы можно было переслать сообщение посредством открытых чатов Пример 1: Входные данные: 5 2 1 2 3 4 Выходные данные: 2 Пример 2: Входные данные: 5 1 1 2 Выходные данные: 3 Пример 3: Входные данные: 5 4 1 2 2 3 3 4 4 5 Выходные данные: 0 0

@LegionK 392 / 262 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	30.06.2021, 15:14	2
	Попробуйте построить граф, вершины которого - составители, а ребра - чаты. Тогда ответом будет количество компонент связности этого графа. Этот алгоритм можно найти в интернете, например на emaxx. 0

@85959594 0 / 0 / 0 Регистрация: 26.06.2021 Сообщений: 8
	30.06.2021, 21:25 [ТС]	3
	Сообщение от LegionK Попробуйте построить граф, вершины которого - составители, а ребра - чаты. Тогда ответом будет количество компонент связности этого графа. Этот алгоритм можно найти в интернете, например на emaxx. можете скинуть ссылку, не смог найти 0

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,067
	30.06.2021, 22:21	4
	Сообщение от LegionK Тогда ответом будет количество компонент связности этого графа. Ответом будет количество компонент связности этого графа минус 1. 0

	30.06.2021, 22:24

Веселые Ребята

Решение