图的存储 链式邻接表

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
struct edge
{
    int u;
    int v;
    int w;
};

vector<edge> e;//边集数组 e[j]存储第j条边的{起点u,终点v,边权w}
vector<int> h[N];//h[u][i]存储u点的所有出边的编号

int n, m;//n个点 m条边
int a, b, c;
void add(int a, int b, int c)
{
    e.push_back({a, b, c});
    h[a].push_back(e.size() -  1);
}

void dfs(int u, int fa)
{
    for(int i = 0; i < h[u].size(); i++)
    {
        int j = h[u][i];
        int v = e[j].v, w = e[j].w;
        if(v == fa) continue;
        printf("%d %d %d\n", u, v, w);
        dfs(v, u);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dfs(1, 0);
    return 0;
}