在许多图论的题目中,我们首先要存图,之前我已经学习了用邻接矩阵存图 ,但是看许多大佬都是用邻接表存图,觉得还是学习下好!

那么我们经过一个例题来学习 邻接链表存图。

N个 输入格式 :
第一行 ,N , M,两个整数,下面M行,每行两个整数,表示一条边 。

输出格式 :
N行 , 第i行 的第一个数 k 表示 有多少边和 i号顶点相连 ,后面 有k个数 , 表示 哪个k个顶点和 i 连接为 一边。

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


struct node{
	int v;
	int next;
}a[maxn]; 

int n,m,p;//p为数组的空余空间下表 
int k[5001],c[5001];//邻接链表表头,k数组记长度 

void add(int u,int v){ // 把 v点插入到 u点的邻接链表 
	a[++p].v = v;  //申请一个新节点 
	a[p].next = c[u];
	c[u] = p;   // 插入到u链表头 
	k[u]++;   //链表长度增加 
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	} 
	for(int i=1;i<=n;i++){
		cout<<k[i]<<" ";
		for(int j =c[i];j>0;j=a[j].next)
		  cout<<a[j].v<<" ";
		  cout<<endl;
	}
	return 0;
} 

测试数据

输入:
5 6
1 3
2 4
1 4
2 3
3 5
2 5

输出:
2 4 3
3 5 3 4
3 5 2 1
2 1 2
2 2 3