# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1084685 | SulA | Pipes (CEOI15_pipes) | C++17 | 1381 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100000];
vector<bool> multi_edge[100000];
int dep[100000], low[100000];
void dfs(int v, int p, bool multi = false) {
low[v] = dep[v] = dep[p] + 1;
for (int j = 0; j < adj[v].size(); j++) {
int ch = adj[v][j];
if (ch == p) continue;
if (dep[ch] == 0) {
dfs(ch, v, multi_edge[v][j]);
low[v] = min(low[v], low[ch]);
} else {
low[v] = min(low[v], dep[ch]);
}
}
if (low[v] == dep[v] && v != p && !multi) {
cout << v+1 << " " << p+1 << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n,m; cin >> n >> m;
while (m--) {
int u,v; cin >> u >> v;
adj[--u].push_back(--v);
adj[v].push_back(u);
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
multi_edge[i].resize(adj[i].size());
for (int j = 0; j < adj[i].size(); j++) {
if (j != 0 && adj[i][j-1] == adj[i][j]) {
multi_edge[i][j] = true;
}
if (j != adj[i].size()-1 && adj[i][j+1] == adj[i][j]) {
multi_edge[i][j] = true;
}
}
}
for (int i = 0; i < n; i++) if (dep[i] == 0) dfs(i, i);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |