제출 #948409

#제출 시각아이디문제언어결과실행 시간메모리
948409vjudge1Pipes (CEOI15_pipes)C++17
10 / 100
203 ms59988 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define all(x) x.begin(), x.end() #define size(x) (int)x.size() template<class S, class T> bool chmin(S &a, const T &b) { return a > b ? (a = b) == b : false; } template<class S, class T> bool chmax(S &a, const T &b) { return a < b ? (a = b) == b : false; } const int N = 5000; bool r[N][N], us[N][N], mul[N][N], vis[N]; int tin[N], fup[N], timer; vector<pair<short, short>> bridges; short n; int m; void dfs(short v, short p = -1) { vis[v] = true; tin[v] = fup[v] = ++timer; for (short to = 0; to < n; ++to) { if (to == p || to == v || !r[v][to]) continue; else if (vis[to]) chmin(fup[v], tin[to]); else { dfs(to, v); chmin(fup[v], fup[to]); if (fup[to] > tin[v]) { bridges.push_back({v, to}); } } } } signed main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m; for (int i = 0; i < m; ++i) { short a, b; cin >> a >> b; a--, b--; r[a][b] = r[b][a] = true; if (us[a][b]) mul[a][b] = mul[b][a] = true; us[a][b] = us[b][a] = true; } for (short i = 0; i < n; ++i) { if (!vis[i]) dfs(i); } for (auto [a, b] : bridges) { if (!mul[a][b]) { cout << a + 1 << ' ' << b + 1 << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...