//
// main.cpp
// C
//
// Created by Sajad Zare on 4/23/22.
//
#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <utility>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <iomanip>
using namespace std;
const int maxn=2e5+2;
int parent[maxn];
int sz[maxn];
map<pair<int, int>, pair<int, pair<int, int>>>s;
vector<int>vic;
int x,y,uu,vv;
set<int>ss;
pair<int, int>h;
pair<int, int>hh;
pair<int, int> get_root(int v){
if (parent[v]!=v){
vic.push_back(v);
parent[v]=get_root(parent[v]).second;
}
if (vic.size()==0){
return {0,parent[v]};
}
else{
return {vic[vic.size()-1],parent[v]};
}
}
void Union(int u,int v){
x=u;
y=v;
h=get_root(u);
vic.clear();
hh=get_root(v);
u=h.second;
v=hh.second;
uu=h.first;
vv=hh.first;
if (u==v){
//cout << x << ' ' << y << endl;
if (uu==0){
//cout << u << endl;
ss.insert(u);
}
if (vv==0){
//cout << v << endl;
ss.insert(v);
}
auto g=s.find({uu,v});
auto gg=s.find({v,uu});
if (g!=s.end()){
s[{uu,v}]={2,{x,y}};
}
if (gg!=s.end()){
s[{v,uu}]={2,{x,y}};
}
auto ggg=s.find({vv,v});
auto gggg=s.find({v,vv});
if (ggg!=s.end()){
s[{vv,v}]={2,{x,y}};
}
if (gggg!=s.end()){
s[{v,vv}]={2,{x,y}};
}
return;
}
else{
s[{u,v}]={1,{x,y}};
if (sz[v]<sz[u]){
parent[v]=u;
sz[u]+=sz[v];
}
else{
parent[u]=v;
sz[v]+=sz[u];
}
}
return;
}
//const int M = 1000000007;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin >> n >> m;
for (int i=1;i<n+1;i++){
parent[i]=i;
sz[i]=1;
}
int u,v;
for (int i=0;i<m;i++){
cin >> u >> v;
Union(u, v);
}
auto z=s.begin();
for (int i=0;i<s.size();i++){
if ((*z).second.first==1 && ss.find((*z).second.second.first)==ss.end() && ss.find((*z).second.second.second)==ss.end()){
cout << (*z).second.second.first << ' ' << (*z).second.second.second << "\n";
}
z++;
}
return 0;
}
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<int, int>, std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int i=0;i<s.size();i++){
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
644 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
363 ms |
564 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
722 ms |
984 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1293 ms |
2104 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1884 ms |
5840 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3105 ms |
6656 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4531 ms |
7884 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5012 ms |
7204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5081 ms |
6880 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
