题解 | 【模板】链式前向星

#include<bits/stdc++.h>
using namespace std;

//链式前向星本质上是通过将连接的边单独存储，而用head存储对应数据的下标来实现高效的读入
//这相比邻接矩阵更节省空间，相比vector由于不用动态开内存速度更快

struct Edge{
	int to,next;
	//to 表示当前节点相连的节点，next是指下一条以相同节点为起点的边在 edge 数组中的下标。
}edge[200005];//无向边开两倍内存因为要创建两次

int head[100005];
int cnt = 0;
// u 表示当前节点 v 表示连接的点
void addedge(int u, int v){
	edge[cnt].to=v;//创建边指点边连接的节点为v
	edge[cnt].next=head[u];//确认下一个连接的点的坐标（由于这里先更新，所以指向的是上一次创建的边的下标方便查询
	head[u] = cnt;//更新下一个连接此节点的下标
	cnt++;
}

int main()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1; i <=n; i++) head[i]=-1;	
	for(int i = 0; i < m; i++)
	{
		int a,b;
		cin >> a >> b;
		addedge(a,b);
		addedge(b,a);
	}
	
	for(int i = 1; i <= n; i++){
		vector<int> neighbors;
		for (int j = head[i]; j != -1; j = edge[j].next) {
			//j!=-1说明这个连接的点还没有读取完， j一直是edge的下标
			neighbors.push_back(edge[j].to);
		}
		
		if (neighbors.empty()) {
			cout << "None" << endl;
		} else {
			int l = neighbors.size();
			sort(neighbors.begin(), neighbors.end());
			for (int k = 0; k < l; k++) {
				cout << neighbors[k] << (k == l - 1 ? "" : " ");
			}
			cout << endl;
		}
	}
}