解法
- Sub 0: 有向グラフにおける，サイクルを求める．
- Sub 1: 有向グラフにおける，最短サイクルを求める．
Sub 0: サイクルを検出するだけなら，DFS, BFS で可能．
Sub 1: 最短のサイクルを求めたいので，BFS を行う． 計算量的には，始点 \(i \in N\) を全探索して BFS をしても間に合う． よって，\(i\) を始点とする BFS をして， サイクル \(i \rightarrow i\) を求める． BFS の途中でサイクルを検出するかもしれないが無視する．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
vvll to(n);
rep(i,m){
ll a,b; cin >> a >> b;
--a, --b;
to[a].push_back(b);
// to[b].push_back(a); // rem: 有向グラフ
}
ll mi = INFL;
vll ans;
rep(i,n){
auto bfs = [&](ll src) -> vll {
vll dis(n, INFL);
vll pre(n, -1);
queue<ll> que;
auto push = [&](ll v, ll d, ll p = -1) -> void {
if(vis[v]) return;
vis[v] = true;
que.push(v);
dis[v] = d;
pre[v] = p;
};
push(src, 0);
while(que.size()){
ll cu = que.front(); que.pop();
ll d = dis[cu];
for(auto ne: to[cu]){
push(ne, d + 1, cu);
}
}
rep(j,n){
for(auto k: to[j]) if(k == src){
if(chmin(mi, dis[j] + 1)){
ans = vll();
ll ind = j;
while(ind != -1){
ans.push_back(ind);
ind = pre[ind];
}
}
}
}
return dis;
};
bfs(i);
}
if(ans.size() != 0){
cout << ans.size() << endl;
for(auto i: ans){
cout << i+1 << endl;
}
}else{
cout << -1 << endl;
}
return 0;
}
