巅峰赛#34 T2 题解

电风扇 T2 为啥是黄。

喵喵喵。
注意到，这是图的广度优先搜索板子。
所以我不讲了。看这个吧。

好吧，也没啥讲的了。
讲讲回环罢。
以下两种都是回环：

讲讲代码罢。
标记正常打。
到最后如果下一个点的编号为 $1$ 就到输出下一个点的步数。
注意要 exit(0)。
不是return 0。
不是return 0。
不是return 0。

注意要输出-1。

喵喵喵。（首尾呼应）

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int n,m,u,v;
vector<int> g[N];
int vis[N];
struct node{
    int num,step;
};
void bfs(){
    queue<node> q;
    q.push({1,0});
    vis[1]=1;
    while (q.size()){
        int un=q.front().num,us=q.front().step;
        q.pop();
        for (int i=0;i<g[un].size();i++){
            int vn=g[un][i],vs=us+1;
            if (vn==1&&us){
                cout<<vs;
                exit(0);
            }
            if (vis[vn]){
                continue;
            }
            q.push({vn,vs});
            vis[vn]=1;
        }
    }
    cout<<-1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
    }
    bfs();
	return 0;
}