Igor
Vyacheslav
Rustam
Rustam
Rustam
сережа
всем привет, решаю учебную задачу: количество компонент связности невзвешенного неориентированного графа, но получаю tl. голову сломал, как сделать быстрее?
извиняюсь, не дополнил: нужно вывести количество компонент, а затем для каждой из них вывести вершины, принадлежащие ей
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> used;
vector<int> colors;
void dfs(int v, int color) {
used[v] = 1;
colors[v] = color;
for (auto u : g[v]) {
if (!used[u]) {
dfs(u, color);
}
}
}
int main() {
cin.tie(nullptr);
int n, m;
cin >> n >> m;
colors.resize(n);
g.resize(n);
used.resize(n);
for (int j = 0; j < m; j++) {
int u, v;
cin >> u >> v;
g[v - 1].push_back(u - 1);
g[u - 1].push_back(v - 1);
}
int color = 0;
for (int j = 0; j < n; j++) {
if (!used[j]) {
dfs(j, color);
}
color++;
}
set<int> dd;
for (int k : colors) {
dd.insert(k);
}
cout << (int)dd.size() << '\n';
for (int k : dd) {
cout << count(colors.begin(), colors.end(), k) << '\n';
for (int j = 0; j < n; j++) {
if (colors[j] == k) {
cout << j + 1 << ' ';
}
}
cout << '\n';
}
return 0;
}
Rustam
всем привет, решаю учебную задачу: количество компонент связности невзвешенного неориентированного графа, но получаю tl. голову сломал, как сделать быстрее?
извиняюсь, не дополнил: нужно вывести количество компонент, а затем для каждой из них вывести вершины, принадлежащие ей
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> used;
vector<int> colors;
void dfs(int v, int color) {
used[v] = 1;
colors[v] = color;
for (auto u : g[v]) {
if (!used[u]) {
dfs(u, color);
}
}
}
int main() {
cin.tie(nullptr);
int n, m;
cin >> n >> m;
colors.resize(n);
g.resize(n);
used.resize(n);
for (int j = 0; j < m; j++) {
int u, v;
cin >> u >> v;
g[v - 1].push_back(u - 1);
g[u - 1].push_back(v - 1);
}
int color = 0;
for (int j = 0; j < n; j++) {
if (!used[j]) {
dfs(j, color);
}
color++;
}
set<int> dd;
for (int k : colors) {
dd.insert(k);
}
cout << (int)dd.size() << '\n';
for (int k : dd) {
cout << count(colors.begin(), colors.end(), k) << '\n';
for (int j = 0; j < n; j++) {
if (colors[j] == k) {
cout << j + 1 << ' ';
}
}
cout << '\n';
}
return 0;
}
А что делается начиная со строчки set<int> dd;?
Igor
сережа
извиняюсь, не дополнил: нужно вывести количество компонент, а затем для каждой из них вывести вершины, принадлежащие ей
Rustam
тогда никакие цвета не нужны, set-ы и так далее
Igor
Nate River
Rustam
tl - это про эффективность выполнения алгоритма, я советую как сделать более оптимально
Rustam
Я же не вижу входных данных задачи и ограничений
Igor
в этом смысл алгоримов ... чтобы оценить не видя входных данных ;)
Rustam
Нет, вы не понимаете о чем говорите.
Igor
всем привет, решаю учебную задачу: количество компонент связности невзвешенного неориентированного графа, но получаю tl. голову сломал, как сделать быстрее?
извиняюсь, не дополнил: нужно вывести количество компонент, а затем для каждой из них вывести вершины, принадлежащие ей
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> used;
vector<int> colors;
void dfs(int v, int color) {
used[v] = 1;
colors[v] = color;
for (auto u : g[v]) {
if (!used[u]) {
dfs(u, color);
}
}
}
int main() {
cin.tie(nullptr);
int n, m;
cin >> n >> m;
colors.resize(n);
g.resize(n);
used.resize(n);
for (int j = 0; j < m; j++) {
int u, v;
cin >> u >> v;
g[v - 1].push_back(u - 1);
g[u - 1].push_back(v - 1);
}
int color = 0;
for (int j = 0; j < n; j++) {
if (!used[j]) {
dfs(j, color);
}
color++;
}
set<int> dd;
for (int k : colors) {
dd.insert(k);
}
cout << (int)dd.size() << '\n';
for (int k : dd) {
cout << count(colors.begin(), colors.end(), k) << '\n';
for (int j = 0; j < n; j++) {
if (colors[j] == k) {
cout << j + 1 << ' ';
}
}
cout << '\n';
}
return 0;
}
Последний цикл в случае если все вершини отдельны квадрат
Igor
сережа
Rustam
В задаче может быть ограничение n до 5000 элементов и пройдет алгоритм за квадрат. Может быть 1e5 и квадрат не пройдет. А вы как в случае и с ссылками пытаетесь умничать в том, в чем не разбираетесь :)
Rustam
Да главное, что вы всё знаете и понимаете :) и оцениваете алгоритм не с точки зрения требований, успехов вам)
сережа
Igor
Rustam
Denis
Всем ку, может кто нибудь помочь найти ошибку в верстке, секция не полностью принимает в себя контейнер с flex wrap wrap и он выходит за ее пределы
сережа
да, попробую реализовать, благодарю
Igor
ты красишь цвета по порядку ... соответсвенно и выводить можешь так же ... без всякого секса
Igor
массив колорс вообще не нужен
Rustam
Igor
Ладно ты молодец .... я лох и опозорился ... все ломает необходимость вывести кол-во цветов. Однако вопро "где тл" ... это не отменяет ;)
Igor
тл был в последнем цикле и для этого не нужно знать ограничения.
Максим
Александр
Подскажите альтернативы jsonkeeper
Maksim Pozharskiy
Александр
Maksim Pozharskiy
late
Всем привет! Что вы думаете про Rust? Есть ли у него будущее? Стоит ли учить для системного программирования или лучше выбрать C++?
Дмитрий
Igor
Шаман Каган
Шаман Каган
ну тогда чего ты колеблешься?
Igor
Шаман Каган
ну коммон ну перейдешь на Го
или еще на что нибудь
просто получай удовольствие
Дмитрий
Меня тоже ломает c# или JavaScript 😁
late
late
Сидредин
late
Сидредин
depre??ed
Можно на индивидуальные уроки по си к Алексею
Bashka
Интернеты х.йню не посоветуют....
Дмитрий
m700
Igor
так я более чем серьезно в данном случае ответил ... считаю что если есть личная убежденность ... спрашивать у людей в сети не стоит. Именно потому что инет во первых токсичен во вторых не компетентен
Igor
лучше уверенно делать ошибки чем бояться сделать шаг
Maksim Pozharskiy
В том формате лучше во флудилку
Сидредин
Сидредин
late
Что можно написать на c++, чего нельзя на Rust?
Igor
лан проехали я переформулировал ... надеюсь все довольны
m700
late
Сидредин
Раст ближе к С или С++? ООП есть в Раст?