B3643 图的存储 题解

Nodellaspkl · 2023-07-20 22:37:35 · 个人记录

题目传送门

分析题意

这道题要求我们存储一个图，并以邻接表和邻接矩阵两种方式输出。

解题思路

一边读入一边以邻接表形式存储。需要注意的是，题目要求以序号顺序输出邻接表，而不是输入顺序。所以需要读入所有边后再处理邻接矩阵。 此外，还要处理节点度数。

\texttt{AC code}

#include <iostream>
#include <vector>
using namespace std;

int n, m;

int gs[1005]; // 度数
vector<int> gv[1005]; // 邻接矩阵
bool gb[1005][1005]; // 邻接表

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        gs[u]++;
        gs[v]++;
        gb[u][v] = 1;
        gb[v][u] = 1;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cout << gb[i][j] << " ";
            if(gb[i][j])
            {
                gv[i].push_back(j);
            }
        }
        cout << endl;
    }
    for(int i = 1; i <= n; i++)
    {
        cout << gs[i] << " ";
        for(int j = 0; j < gs[i]; j++)
        {
            cout << gv[i][j] << " ";
        }

        cout << endl;
    }
    return 0;
}