树与图的存储与遍历

树与图的存储

树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。

(1) 邻接矩阵：g[a][b] 存储边a->b，所有边初始化为正无穷

(2) 邻接表：

1
2
3
4
5
6
7
8
9
10
11
12
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的遍历

时间复杂度 O(n+m), n 表示点数，m 表示边数。

深度优先遍历

1
2
3
4
5
6
7
8
9
10
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

排列数字

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例：
1
3
输出样例：
1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
int record[10];
vector<int>path;
int n;

void say() {
	for (int i = 0; i < path.size(); i++) {
		printf("%d ", path[i]);
	}
	cout<<endl;
}
void dfs() {
	if (path.size() == n) {
		say();
	} else {
		for (int i = 1; i <= n; i++) {
			if (record[i] == 0) {
				record[i] = 1;
				path.push_back(i);
				dfs();
                // 回溯
				path.pop_back();
				record[i] = 0;
			}
		}
	}
}

int main() {
	cin>>n;
	dfs();
}
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>

using namespace std;

const int N = 10;

int n;
int path[N];

void dfs(int u, int state)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        puts("");

        return;
    }

    for (int i = 0; i < n; i ++ )
        if (!(state >> i & 1))
        {
            path[u] = i + 1;
            dfs(u + 1, state + (1 << i));
        }
}

int main()
{
    scanf("%d", &n);

    dfs(0, 0);

    return 0;
}

n-皇后问题

n皇后问题是指将 n个皇后放在 n×n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

1_597ec77c49-8-queens.png

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例：
1
4
输出样例：
1
2
3
4
5
6
7
8
9
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
vector<int>path;
int res = 0;
int n;
// 相当于对一个路线在加上一个新的皇后后形成的图
vector<vector<int>> build(vector<vector<int>> road) {
	int x = path.size() - 1;
	int y = path[x];
	for (int i = x + 1; i < n; i++) {
		road[i][y] = 1;
	}
	for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) {
		road[i][j] = 1;
	}
	for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) {
		road[i][j] = 1;
	}
	return road;
}

void say() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (path[i] == j) {
				cout << "Q";
			} else {
				cout << ".";
			}
		}
		cout << endl;
	}
	cout << endl;

}
void dfs(vector<vector<int>> road) {
	if (path.size() == n) {
		say();
		return;
	};
	int cur_x = path.size();
	for (int i = 0; i < n; i++) {
		if (road[cur_x][i] != 1) {
			path.push_back(i);
			dfs(build(road));
			path.pop_back();
		}
	}

}

int main() {
	cin >> n;
	dfs(vector<vector<int>>(n, vector<int>(n, 0)));
}
板子

  • 第一种

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    #include <iostream>

    using namespace std;

    const int N = 10;

    int n;
    bool row[N], col[N], dg[N * 2], udg[N * 2];
    char g[N][N];

    void dfs(int x, int y, int s)
    {
        if (s > n) return;
        if (y == n) y = 0, x ++ ;

        if (x == n)
        {
            if (s == n)
            {
                for (int i = 0; i < n; i ++ ) puts(g[i]);
                puts("");
            }
            return;
        }

        g[x][y] = '.';
        dfs(x, y + 1, s);

        if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
        {
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
            g[x][y] = 'Q';
            dfs(x, y + 1, s + 1);
            g[x][y] = '.';
            row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        }
    }

    int main()
    {
        cin >> n;

        dfs(0, 0, 0);

        return 0;
    }

  • 第二种

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include <iostream>

    using namespace std;

    const int N = 20;

    int n;
    char g[N][N];
    bool col[N], dg[N], udg[N];

    void dfs(int u)
    {
        if (u == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
            return;
        }

        for (int i = 0; i < n; i ++ )
            if (!col[i] && !dg[u + i] && !udg[n - u + i])
            {
                g[u][i] = 'Q';
                col[i] = dg[u + i] = udg[n - u + i] = true;
                dfs(u + 1);
                col[i] = dg[u + i] = udg[n - u + i] = false;
                g[u][i] = '.';
            }
    }

    int main()
    {
        cin >> n;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                g[i][j] = '.';

        dfs(0);

        return 0;
    }

树的重心

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 n，表示树的结点数。

接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。

输出格式

输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

1≤n≤1e5

输入样例
1
2
3
4
5
6
7
8
9
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
1
4
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
1#include<bits/stdc++.h>
using namespace std;
const int N = 200100;
int e[N], f[N], ne[N], indexs = 0;
int val[N];
void insert(int a, int b) {
    // 声明一个边的坐标并告诉这条边的终点时b
	e[++indexs] = b;
    // 声明这条边的下一条边是原先以a作为起始点的第一条边
	ne[indexs] = f[a];
    // 声明以a作为起始点的第一条边是它
	f[a] = indexs;
}

/*
	稍微复习了一下数据的存储
	e[i] 代表第i条边的目的地是 e[i]
	ne[i] 代表和第i条边同一起始点的下一条边为ne[i]
	f[i] 代表以i作为点的第一条边是f[i]
*/

// 这个函数的目的是以某个点做树的根节点算出他的节点数
int build(int x) {
	val[x] = 1;
	for (int i = f[x]; i != 0; i = ne[i]) {
		if (val[e[i]] == 0) {
			val[x] += build(e[i]);
		}
	}
	return val[x];
}

int main () {
	int n;
	cin >> n;
	int a, b;
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		insert(a, b);
		insert(b, a);
	}
	build(a);
	int ans = INT_MAX;

	for (int i = 1; i <= n; i++) {
		int cnt = INT_MIN;
        // 这道题的本质就是计算某个点作为树节点 他的左右孩子节点的权值 和总权值出去他后最大权值的最小值
		for (int b = f[i]; b != 0; b = ne[b]) {
			if (val[e[b]] > val[i]) {
				cnt = max(cnt, n - val[i]);
			} else {
				cnt = max(cnt, val[e[b]]);
			}

		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
}
/*

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


*/
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 这里dfs结果是以某个点为树根后他的权值
int dfs(int u)
{
    st[u] = true;

    int size = 0, sum = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;

        int s = dfs(j);
        // 这里是计算的以某个点为取消点后 他的子节点的权值 最大值
        size = max(size, s);
        // 这里计算的是全部字节点的和
        sum += s;
    }

    //这里我们得到以某个点为取消点后的结果
    size = max(size, n - sum - 1);
    ans = min(ans, size);

    return sum + 1;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(1);

    printf("%d\n", ans);

    return 0;
}
/*
	结论旗差一招，我们可以在得出结论之和直接进行计算无需存储
*/

宽度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

走迷宫

给定一个 n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0或 1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例：
1
2
3
4
5
6
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
1
8
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
int main() {
	int len = 0;
	int n, m;
	cin >> n >> m;
	int nextRoad[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	vector<vector<int>>road(n + 1, vector<int>(m + 1, 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> road[i][j];
		}
	}

	queue<PII> que;
	que.push({1, 1});
	while (!que.empty()) {
		int size = que.size();
		for (int i = 0; i < size; i++) {
			PII cur = que.front();
			que.pop();
			if (cur.first == n && cur.second == m) {
				cout << len << endl;
				return 0;
			}

			for (int i = 0; i < 4; i++) {
				PII ne = {cur.first + nextRoad[i][0],
				          cur.second + nextRoad[i][1]
				         };
				if (ne.first <= n && ne.first > 0 && ne.second <= m && ne.second > 0 && road[ne.first][ne.second] == 0) {
					que.push(ne);
					road[ne.first][ne.second] = 1;
				}
			}

		}
		len++;
	}
}
/*
	5 5
	0 1 0 0 0
	0 1 0 1 0
	0 0 0 0 0
	0 1 1 1 0
	0 0 0 1 0
*/
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
int g[N][N], d[N][N];

int bfs()
{
    queue<PII> q;

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }

    return d[n - 1][m - 1];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}

八数码

在一个 3×33×3 的网格中，1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如：

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

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

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

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

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

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式

输入占一行，将 3×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

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

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1。

输入样例：
1
2 3 4 1 5 x 7 6 8
输出样例
1
19
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
using namespace std;
/*
	本体的关注点应该在如何去交换，如何判断是否出现过上，考虑到vector的是否存在过判断耗时，我决定采用string,我们先声明一个队列（ps：用于广搜）一个set(ps：用于判断是否出现过)，考虑到每一次交换都要先找出x的位置可能会使耗时*8我们可以额外申请一个存储x位置的空间与字符串进行组合，剩下的就是广搜的思路了注意这里交换的化要考虑是否满足交换条件（ps，如果x向左交换需要判断左侧是否有数据）。
*/
bool isValid(string num) {
	for (int i = 1; i <= 8; i++) {
		if (num[i] != i + '0') return false;
	}
	return true;
}

string myswap(string s, int aim, int from) {
	string get = s;
	swap(get[aim], get[from]);
	char aim_x = '0' + aim;
	get[s.size() - 1] = aim_x;
	return get;
}
int main() {
	set<string> happen;
	queue<string>que;
	string now;
	now = " ";
	int len = 0;
	char x_index;
	for (int i = 1; i <= 9; i++) {
		char s;cin>>s;
		now += s;
		if (s == 'x') {
			x_index = i + '0';
		}
	}
	now += x_index;
	happen.insert(now);
	que.push(now);

	while (!que.empty()) {
		int size = que.size();

		for (int i = 0; i < size; i++) {
			string front = que.front();
			que.pop();
			if (isValid(front)) {
				cout << len << endl;
				return 1;
			}
			int index = front[front.size() - 1] - '0';

			//			上
			if (index > 3) {
				string get = myswap(front, index - 3, index);

				if (!happen.count(get)) {
					happen.insert(get);
					que.push(get);
				}
			}
			//			下
			if (index < 7) {
				string get = myswap(front, index + 3, index);
				if (!happen.count(get)) {
					happen.insert(get);
					que.push(get);
				}
			}
			//			左
			if (index % 3 != 1) {
				string get = myswap(front, index - 1, index);
				if (!happen.count(get)) {
					happen.insert(get);
					que.push(get);
				}
			}
			//			右
			if (index % 3 != 0) {
				string get = myswap(front, index + 1, index);
				if (!happen.count(get)) {
					happen.insert(get);
					que.push(get);
				}
			}
		}
		len++;

	}
	cout<<-1<<endl;
}
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

int bfs(string state)
{
    queue<string> q;
    /*
    	用一个map即实现了位置和存在的寻找
    */
    unordered_map<string, int> d;

    q.push(state);
    d[state] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    /*
    	用一个字符串相等绝杀我的函数
    */
    string end = "12345678x";
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        if (t == end) return d[t];

        int distance = d[t];
        // 用一个find导致我开辟的空间像个傻子
        int k = t.find('x');
        // 用一个坐标转化加·数字让我的上下左右像个呆瓜
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[a * 3 + b], t[k]);
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]);
            }
        }
    }

    return -1;
}

int main()
{
    char s[2];

    string state;
    for (int i = 0; i < 9; i ++ )
    {
        cin >> s;
        state += *s;
    }

    cout << bfs(state) << endl;

    return 0;
}

图中点的层次

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围

1≤n,m≤1e5

输入样例：
1
2
3
4
5
6
4 5
1 2
2 3
3 4
1 3
1 4
输出样例：
1
1
代码
个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int N = 100100;
int e[N],ne[N],f[N],idx = 0;
int record[N];
void add(int a, int b) {
	e[++idx] = b;
	ne[idx] = f[a];
	f[a] = idx;
}

int main() {
	int n,m;cin>>n>>m;
	int len = 0;
	while(m--){
		int a,b;cin>>a>>b;
		add(a,b);a
	record[1] = 1;
	queue<int>que;
	que.push(1);
	while(!que.empty()){
		int size = que.size();
		for(int i=0;i<size;i++){
			int top = que.front();que.pop();
			if (top == n) {
				cout<<len<<endl;
				return 0;
			}
			for(int b = f[top];b!=0;b=ne[b]){
				if (record[e[b]] == 0) {
					record[e[b]] = 1;
					que.push(e[b]);
				}		
			}
		}
		len++;
	}
	cout<<-1<<endl;
}
/*
4 5
1 2
2 3
3 4
1 3
1 4
*/
    
    /*
    	感悟，本体存在两个核心问题 1： 如何标记有向图；2：出现环的处理方式
    	add只加一次利用一个record记录那个点是否出现过来防止环的发生
    */
板子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs()
{
    memset(d, -1, sizeof d);

    queue<int> q;
    d[1] = 0;
    q.push(1);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1)
            {
                d[j] = d[t] + 1;
                q.push(j);
            }
            // 对于record函数他又更好的利用不单单是零和1板子给他赋予了距离的含有让我们不需要纠结与len限制于层序遍历
        }
    }

    return d[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}