結果
問題 | No.1023 Cyclic Tour |
ユーザー |
![]() |
提出日時 | 2020-04-10 22:50:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,810 bytes |
コンパイル時間 | 1,063 ms |
コンパイル使用メモリ | 90,484 KB |
実行使用メモリ | 24,320 KB |
最終ジャッジ日時 | 2024-09-15 23:10:12 |
合計ジャッジ時間 | 11,239 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 27 WA * 22 |
ソースコード
#include <iostream>#include <vector>#include <set>#include <stack>using namespace std;using Graph = vector<vector<int>>;// 探索vector<bool> seen, finished;// サイクル復元のための情報int pos = -1; // サイクル中に含まれる頂点 posstack<int> hist; // 訪問履歴void dfs(const Graph &G, int v, int p) {seen[v] = true;hist.push(v);for (auto nv : G[v]) {if (nv == p) continue; // 逆流を禁止する// 完全終了した頂点はスルーif (finished[nv]) continue;// サイクルを検出if (seen[nv] && !finished[nv]) {pos = nv;return;}// 再帰的に探索dfs(G, nv, v);// サイクル検出したならば真っ直ぐに抜けていくif (pos != -1) return;}hist.pop();finished[v] = true;}int main() {// 頂点数 (サイクルを一つ含むグラフなので辺数は N で確定)int N; cin >> N;int M; cin >> M;// グラフ入力受取Graph G(N);for (int i = 0; i < M; ++i) {int a, b, c;cin >> a >> b >> c;--a; --b; // 頂点番号が 1-indexed で与えられるので 0-indexed にするG[a].push_back(b);if(c == 1) G[b].push_back(a);}// 探索seen.assign(N, false); finished.assign(N, false);pos = -1;dfs(G, 0, -1);// サイクルを復元set<int> cycle;while (!hist.empty()) {int t = hist.top();cycle.insert(t);hist.pop();if (t == pos) break;}// クエリに答えるfor(int i = 0; i < N; i++){if (cycle.count(i)){cout << "Yes" << endl;return 0;}}cout << "No" << endl;return 0;}