图（邻接表法）

图的表示方法有很多，这里有一种比较常见的用法：邻接表法，它的实现往往在竞赛中不用链表，而是通过vector动态数组实现

表示方法：

vector<int>a[10]；//表示有10个结点，其中每个结点对应的vector里存放与它相连的结点

例题1：求各点到1号点的最短距离

测试数据：

7 6
1 2
2 4
1 3
2 5
3 7
3 6

 /*邻接表 bfs 最短距离*/
 #include<bits/stdc++.h>
 #include<vector>
 using namespace std;
 int n,m;
 vector<int>a[10];
 bool vis[12];
 int dis[12];//记录步数
queue<int> q;
void bfs(int st){
	q.push(st);
	vis[st]=1;
	memset(dis,0x3f,sizeof(dis));
	dis[st]=0;//起点的步数为0
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(auto to:a[now]){
			if(!vis[to]){
				dis[to]=min(dis[to],dis[now]+1);
				q.push(to);
				vis[to]=1;
			}
		}
	}
}
 int main(){
 	cin>>n>>m;
 	int u,v;
 	for(int i=1;i<=m;i++){
 		cin>>u>>v;
 		a[u].push_back(v);//无向图，需要两次
 		a[v].push_back(u);
	 }
	 bfs(1);
	 /*求最短距离的*/
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	 return 0;
 }
 /*
7 6
1 2
2 4
1 3
2 5
3 7
3 6
 */

例题2：图的遍历（普及+/提高）

题目描述

给出N个点，M条边的有向图，对于每个点v*，求A(v)表示从点vv出发，能到达的编号最大的点。

输入格式

第1 行，2 个整数N,M*。

接下来M行，每行2个整数U_i,V_iU**i,V**i，表示边(U_i,V_i)(U**i,V**i)。点用1, 2,\cdots,N1,2,⋯,N编号。

输出格式

N 个整数A(1),A(2),\cdots,A(N)A(1),A(2),⋯,A(N)。

输入输出样例

输入 #1复制

4 3
1 2
2 4
4 3

输出 #1复制

4 4 3 4

说明/提示

• 对于60% 的数据，1 \le N . M \le 10^31≤N.M≤103；

• 对于100% 的数据，1 \le N , M \le 10^51≤N,M≤105。

大佬题解：反向建边 + dfs

按题目来每次考虑每个点可以到达点编号最大的点，不如考虑较大的点可以反向到达哪些点

循环从N到1，则每个点i能访问到的结点的A值都是i

每个点访问一次，这个A值就是最优的，因为之后如果再访问到这个结点那么答案肯定没当前大了

#include<bits/stdc++.h>
using namespace std;
vector<int> vv[100005];
int dis[100005];
int n,m;
void dfs(int x,int d){
	if(dis[x]){
		return;
	}
	dis[x]=max(dis[x],d);
	for(int i=0;i<vv[x].size();i++){
		dfs(vv[x][i],d);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		vv[v].push_back(u); 
	}
	//memset(dis,0x7fffffff,sizeof(dis));
	for(int i=n;i>=1;i--){
		dfs(i,i);
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

例题3：图的两种遍历方式

小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 n(n\le10^5)n(n≤105) 篇文章（编号为 1 到 nn）以及 m(m\le10^6)m(m≤106) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

输入格式

无

输出格式

无

输入输出样例

输入 #1复制

8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8

输出 #1复制

1 2 5 6 3 7 8 4 
1 2 3 4 5 6 7 8 

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> A[100005];
bool book[100005];
queue<int> qu;
void dfs(int x){
	if(book[x]){
		return;
	}
	book[x]=1;
	cout<<x<<" ";
	for(int i=0;i<A[x].size();i++){
		dfs(A[x][i]);
	}
}
void bfs(int x){
	qu.push(x);
	book[x]=1;
	while(!qu.empty()){
		int now=qu.front();
		cout<<now<<" ";
		qu.pop();
		for(int i=0;i<A[now].size();i++){
			if(!book[A[now][i]]){
				book[A[now][i]]=1;
				qu.push(A[now][i]);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		A[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		sort(A[i].begin(),A[i].end());
	}
	dfs(1);
	cout<<endl;
	memset(book,0,sizeof(book));
	bfs(1);
}