有向グラフのサイクル検出
トポロジカルソートと同じ．DFS,BFSでも可能．
DFSによる実装
頂点 \(i\) に対して， \(val_{i}\) を
- 0 : 訪れてない
- 1 : 訪れたが計算途中
- 2 : 訪れて計算が終わった
として保持する． \(val_{i} = 1\) の状態で再び訪れたらサイクルということ．
遷移するとき，if(ne != pa)の部分は不要．
BFSによる実装
入次数を保持しておく． 頂点に訪れたら，そこに入った辺は二度と使わないので，入次数を-1する． 入次数が0になった頂点を追加していく．
トポロジカルソート可能であることは， BFSが終わった時点で全ての頂点を訪れているのが必要十分．
実装上の注意
サイクルの長さが1,2の場合はコーナーケースになりやすい．
使っている記号，マクロ等 "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);
}
vll val(n);
if(val[cu] == 1){
return true;
}else if(val[cu] == 2){ // 枝狩
return false;
}
val[cu] = 1;
if(f(f, ne, cu)) return true;
}
val[cu] = 2;
return false;
};
rep(i,n) if(val[i] == 0){
if(dfs(dfs, i)){
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}
