| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 246420 | dantoh000 | Pipes (CEOI15_pipes) | C++14 | 0 ms | 0 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 <utility>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;
typedef pair<int,int> ii;
int n,m;
int d[100005], pa[100005], sz[100005];
vector<int> G[100005];
set<ii> bad;
struct ufds{
int p[100005];
ufds(){
for (int i = 0; i <= 100000; i++) p[i] = i;
}
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
void un(int x, int y){
p[x] = y;
}
} u1 = ufds(), u2 = ufds();
void dfs(int u, int p){
///join at side bad
u2.p[u] = u;
pa[u] = p;
for (auto v : G[u]){
if (v == p) continue;
else{
d[v] = d[u]+1;
pa[v] = u;
dfs(v,u);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i = 0; i < m; i++){
int u,v;
scanf("%d%d",&u,&v);
int pu = u1.find(u), pv = u1.find(v);
//printf("%d -> %d, %d -> %d\n",u,pu,v,pv);
if (pu == pv){
//printf("update path %d %d\n",u,v);
///make all edges along this path bad
///all edges along path are only changed once, amortised O(N)
u = u2.find(u), v = u2.find(v);
while (u != v){
if (d[u] < d[v]) swap(u,v);
bad.insert({min(u,pa[u]),max(u,pa[u])});
//printf("bad %d %d\n",u,pa[u]);
u2.un(u, pa[u])
u = pa[u];
u = u2.find(u);
}
}
else{
//printf("join %d %d\n",u,v);
///join the two components
if (sz[pu] < sz[pv]){
swap(pu,pv);
swap(u,v);
}
///join small v to big u
u1.un(pv,pu);
sz[pu] += sz[pv];
///add edge
G[u].push_back(v);
G[v].push_back(u);
///restart dfs
d[v] = d[u]+1;
dfs(v,u);
}
}
for (int u = 1; u <= n ;u++){
for (auto v : G[u]){
if (v > u && bad.find({u,v}) == bad.end()){
printf("%d %d\n",u,v);
}
}
}
}