//In the name of Allah
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
typedef pair < int , int > pii;
const int N = 1e5 + 10;
int par[2][N], sz[2][N], mark[N], h[N], dp[N];
vector < pii > adj[N];
int getPar(int t, int v){
return par[t][v] == v ? v : par[t][v] = getPar(t, par[t][v]);
}
bool merge(int t, int u, int v){
u = getPar(t, u); v = getPar(t, v);
if (u == v)
return false;
if (sz[t][v] < sz[t][u])
swap(u, v);
par[t][u] = v;
sz[t][v] += sz[t][u];
return true;
}
void DFS(int v, int p = -1){
mark[v] = 1;
dp[v] = N;
int u, id;
for (pii e : adj[v]){
u = e.X; id = e.Y;
if (id == p)
continue;
if (mark[u])
dp[v] = min(dp[v], h[u]);
else{
h[u] = h[v] + 1;
DFS(u, id);
dp[v] = min(dp[v], dp[u]);
if (h[v] < dp[u])
cout << u << ' ' << v << '\n';
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < N; i ++)
par[0][i] = par[1][i] = i, sz[0][i] = sz[1][i] = 1;
int u, v;
for (int i = 0; i < m; i ++){
cin >> u >> v;
if (merge(0, u, v)){
adj[u].pb(mp(v, i));
adj[v].pb(mp(u, i));
}
else if (merge(1, u, v)){
adj[u].pb(mp(v, i));
adj[v].pb(mp(u, i));
}
}
for (v = 1; v <= n; v ++)
if (!mark[v])
DFS(v);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4204 KB |
Output is correct |
2 |
Correct |
3 ms |
4224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
4844 KB |
Output is correct |
2 |
Correct |
9 ms |
4716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
114 ms |
4716 KB |
Output is correct |
2 |
Correct |
111 ms |
4588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
199 ms |
5504 KB |
Output is correct |
2 |
Correct |
222 ms |
5100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
317 ms |
7276 KB |
Output is correct |
2 |
Runtime error |
296 ms |
20588 KB |
Memory limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
486 ms |
13292 KB |
Output is correct |
2 |
Runtime error |
427 ms |
28012 KB |
Memory limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
674 ms |
14700 KB |
Output is correct |
2 |
Runtime error |
668 ms |
44524 KB |
Memory limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
951 ms |
17260 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1084 ms |
17132 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1317 ms |
36756 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |