有向グラフがDAGである場合は"Yes"
を、閉路を含む場合は"No"
を出力するコードです。DAGであるときは、x
にトポロジカルソートの結果が入ります。していることはBFSですが、キューを使わないことでグラフの辿る順序を保存できています。面白いです。
#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int>> g(n); vector<int> deg(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); deg[v]++; } vector<int> x; for (int i = 0; i < n; i++) { if (deg[i] == 0) { x.push_back(i); } } for (int i = 0; i < x.size(); i++) { int u = x[i]; for (auto v : g[u]) { if (--deg[v] == 0) { x.push_back(v); } } } if (x.size() == n) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }