图的邻接表 BFS 搜索模板

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

const int N = 1005;              // 根据题目点的数量范围调整
vector<int> adj[N];              // 邻接表（有权图需要使用结构体）
bool vis[N];
int step[N];
int n, m, st, ed;

void bfs() {
	vis[st] = 1;
	queue<int> q;
	q.push(st);
	
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v : adj[u]) {
			if (vis[v]) continue;
			step[v] = step[u] + 1;
			vis[v] = 1;
			if (v == ed) return;   // 到达终点提前返回
			q.push(v);
		}
	}
}

int main() {
	cin >> n >> m >> st >> ed;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		// 无向图需要反向边
		// adj[v].push_back(u);       
	}
	
	bfs();
	if (!vis[ed]) cout << -1 << endl;  // 不可达输出 -1
	else cout << step[ed] << endl;
	return 0;
}