結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2023-06-12 14:41:12 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,596 bytes |
コンパイル時間 | 1,583 ms |
コンパイル使用メモリ | 135,076 KB |
実行使用メモリ | 35,376 KB |
最終ジャッジ日時 | 2024-06-11 16:25:18 |
合計ジャッジ時間 | 14,161 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 WA * 108 |
ソースコード
#include <algorithm>#include <iostream>#include <stack>#include <string.h>#include <vector>#include <map>using namespace std;typedef vector <vector<int>> Graph;const int MAX_N = 100000;int root;bool visited[MAX_N];bool finished[MAX_N];void dfs(int u, int parent, const Graph &G, stack<int> &path) {visited[u] = true;path.push(u);for (int v : G[u]) {if (v == parent) continue;if (finished[v]) continue;if (visited[v] && !finished[v]) {root = v;return;}dfs(v, u, G, path);if (root != -1) return;}path.pop();finished[u] = true;}vector<int> cycle_detection(int start, const Graph &G) {root = -1;memset(visited, false, sizeof(visited));memset(finished, false, sizeof(finished));stack<int> path;dfs(start, -1, G, path);vector<int> res;while (!path.empty()) {res.push_back(path.top());path.pop();}return res;}int main() {int N;cin >> N;Graph G(N + 1);map<int, map<int, int>> E;int a, b;for (int i = 0; i < N; ++i) {cin >> a >> b;E[a][b] = i + 1;E[b][a] = i + 1;G[a].push_back(b);G[b].push_back(a);}vector<int> path = cycle_detection(1, G);if (path.empty()) {cout << -1 << endl;} else {int L = path.size();vector<int> ids;for (int i = 0; i < L; ++i) {int u = path[i];int v = path[(i + 1) % L];ids.push_back(E[u][v]);}sort(ids.begin(), ids.end());cout << L << endl;for (int id : ids) {cout << id << " ";}cout << endl;}return 0;}