От матрицы смежности к спискам смежности

@Kaiser3621 · Регистрация: 11.10.2022

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

Задача №112628. Списки смежности из матрицы
Напишите программу, которая строит списки смежности для каждой вершины графа на основе его матрицы смежности.

Входные данные
В первой строке вводится количество вершин графа N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа.

Выходные данные
Программа должна вывести списки смежности для каждой вершины графа в порядке возрастания их номеров. Номера вершин в каждом списке разделены пробелами. Нумерация начинается с единицы. Если из вершины не выходит ни одно ребро, вместо списка нужно вывести число 0.

Примеры
входные данные
5
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
0 0 0 0 0
0 1 0 1 0
выходные данные
2 3 4
1 3 5
1 2 4
0
2 4
почему мой код не даёт правильный ответ и тем самым даёт частичное решение

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;  // Считываем размерность матрицы
    vector<vector<int>> Matrix(n, vector<int>(n));
 
    // Заполняем матрицу Matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> Matrix[i][j];
        }
    }
 
    vector<vector<int>> List(n);
 
    // Заполняем вектор List на основе матрицы Matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (Matrix[i][j] == 1) {
                List[i].push_back(j + 1);
            }
        }
    }
 
    // Выводим результат
    for (int i = 0; i < n; ++i) {
        cout << List[i].size();
        for (auto j = 0u; j < List[i].size(); ++j) {
            cout << " " << List[i][j];
        }
        cout << endl;
    }
 
    return 0;
}

@Salo__Salo · 12.08.2023, 20:39

ты каждый раз выводишь длину строки, ее нужно выводить лишь тогда , когда строка пуста:

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;  // Считываем размерность матрицы
    vector<vector<int>> Matrix(n, vector<int>(n));
 
    // Заполняем матрицу Matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> Matrix[i][j];
        }
    }
 
    vector<vector<int>> List(n);
 
    // Заполняем вектор List на основе матрицы Matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (Matrix[i][j] == 1) {
                List[i].push_back(j + 1);
            }
        }
    }
 
    // Выводим результат
    for (int i = 0; i < n; ++i) {
        if (List[i].empty()) { // Если список смежных вершин не пуст
            cout << List[i].size() << endl;
    
        }
            else{
            for (auto j = 0u; j < List[i].size(); ++j) {
                cout << List[i][j] << " ";
            }
 
        cout << endl;
    }
    }
 
    return 0;
}

@SmallEvil · 12.08.2023, 21:35

Kaiser3621, Salo__Salo, зачем создавать этот список смежности и ту же матрицу, если просто нужно вывести данные ?

C++

#include <iostream>
int main(){
    using std::cin; using std::cout; using std::endl;
    int n, v, w, edges, vertex;
    cin >> n;
    for(v = 0; v!=n; ++v){
        for(w = 0, edges = 0; w!=n; ++w){
            cin >> vertex;
            if (vertex){
                cout << w+1 << ' ';
                ++edges;
            }
        }
        edges ? cout << endl : cout << '0' << endl; 
    }
}

Новые блоги и статьи
Элементы алгоритмизации hw_wired 28.01.2025 Основы алгоритмизации В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .	Человек и информация hw_wired 28.01.2025 Введение: роль информации в познании мира В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .	Компьютер и информация hw_wired 28.01.2025 Эволюция вычислительных машин История развития вычислительной техники начинается задолго до появления первых электронных устройств. Человечество всегда стремилось упростить процесс вычислений и. . .	Информационные технологии hw_wired 28.01.2025 Введение в современные технологии работы с информацией В современном мире информационные технологии стали неотъемлемой частью практически всех сфер человеческой деятельности. Они существенно. . .	Информация вокруг нас hw_wired 28.01.2025 Основные понятия информации В современном мире понятие информации является фундаментальным и охватывает практически все сферы человеческой деятельности. Информация представляет собой совокупность. . .	Компьютер для начинающих hw_wired 28.01.2025 Введение в мир компьютерных технологий В современном мире информация стала одним из важнейших ресурсов человечества, определяющим развитие общества и технологий. Наша жизнь неразрывно связана с. . .
[golang] 189. Rotate Array alhaos 28.01.2025 Повороты рукоятки, целочисленный слайс нужно сдвинуть на целое положительное число. Мне очень нравится решение на GO / / https:/ / leetcode. com/ studyplan/ top-interview-150/ package topInterview . . .	КуМир: решение задач на матрицы bytestream 28.01.2025 КуМир представляет собой среду для обучения программированию, которая включает в себя мощные инструменты для работы с матрицами. Матрица в программировании - это двумерный массив, состоящий из. . .	КуМир: решение задач на строки bytestream 28.01.2025 В системе программирования КуМир работа со строковыми данными является одним из важнейших аспектов создания программ. Строки представляют собой последовательности символов, заключенные в кавычки,. . .	КуМир: решение геометрических задач bytestream 28.01.2025 Программирование геометрических задач в среде КуМир становится всё более актуальным в обучении школьников и студентов. КуМир — это разработанная в России обучающая программная среда, предназначенная. . .	КуМир, исполнитель Водолей: Задачи и решения bytestream 28.01.2025 КуМир — это образовательная среда для обучения программированию. Она предлагает пользователям разнообразные инструменты для разработки и отладки программ, что особенно ценно для студентов и. . .	КуМир, исполнитель Чертежник: Решение задач bytestream 28.01.2025 КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения основам программирования и алгоритмизации. Исполнитель Чертежник работает на координатной плоскости, где может. . .

	12.08.2023, 21:35

От матрицы смежности к спискам смежности

Решение