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

@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; 
    }
}

	12.08.2023, 21:35

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

Решение