# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
154232 | arnold518 | Pipes (CEOI15_pipes) | C++14 | 1781 ms | 13756 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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
struct UF
{
int par[MAXN+1];
UF() { for(int i=0; i<=MAXN; i++) par[i]=i; }
int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
x=Find(x); y=Find(y);
par[x]=y;
}
};
UF uf1, uf2;
int N, M;
vector<int> adj[MAXN+1];
int idx[MAXN+1], cnt=1;
int dfs(int now, int bef)
{
idx[now]=cnt++;
int ret=idx[now];
int k=0;
for(int nxt : adj[now])
{
if(nxt==bef) { k++; continue; }
if(idx[nxt]!=0) ret=min(ret, idx[nxt]);
else
{
int t=dfs(nxt, now);
ret=min(ret, t);
if(t>idx[now]) printf("%d %d\n", now, nxt);
}
}
if(k>1) ret=min(ret, idx[bef]);
return ret;
}
int main()
{
int i, j;
scanf("%d%d", &N, &M);
while(M--)
{
int u, v;
scanf("%d%d", &u, &v);
if(uf1.Find(u)!=uf1.Find(v)) uf1.Union(u, v), adj[u].push_back(v), adj[v].push_back(u);
else if(uf2.Find(u)!=uf2.Find(v)) uf2.Union(u, v), adj[u].push_back(v), adj[v].push_back(u);
}
for(i=1; i<=N; i++) if(idx[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... |