結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2023-06-12 14:50:24 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,825 bytes |
コンパイル時間 | 1,494 ms |
コンパイル使用メモリ | 135,624 KB |
実行使用メモリ | 42,976 KB |
最終ジャッジ日時 | 2024-06-11 16:32:37 |
合計ジャッジ時間 | 18,000 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 121 TLE * 1 -- * 1 |
ソースコード
#include <algorithm>#include <iostream>#include <stack>#include <string.h>#include <vector>#include <map>#include <climits>using namespace std;typedef vector <vector<int>> Graph;const int MAX_N = 100001;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 minV = INT_MAX;vector<int> res;for (int v : path) {vector<int> p = cycle_detection(v, G);int s = p.size();if (minV > s) {minV = s;res = p;}}int L = res.size();vector<int> ids;for (int i = 0; i < L; ++i) {int u = res[i];int v = res[(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;}