#include <bits/stdc++.h>
#pragma GCC opimize("O3")
using namespace std;
vector<vector<int>> muchii1,muchii2;
vector<int> nodes;
int comp1[100005],comp2[100005],lg1[100005],lg2[100005];
bool use[100005];
int n,m;
void dfs(int nod)
{
use[nod]=1;
comp2[nod]=lg1[nod];
for(int z=0;z<muchii1[nod].size();z++)
{
int node=muchii1[nod][z];
if(node==comp1[nod])
continue;
if(!use[node])
{
comp1[node]=nod;
lg1[node]=lg1[nod]+1;
dfs(node);
comp2[nod]=min(comp2[nod],comp2[node]);
}
else
comp2[nod]=min(comp2[nod],lg1[node]);
}
for(int z=0;z<muchii2[nod].size();z++)
{
int node=muchii2[nod][z];
if(node==comp1[nod])
continue;
if(!use[node])
{
comp1[node]=nod;
lg1[node]=lg1[nod]+1;
dfs(node);
comp2[nod]=min(comp2[nod],comp2[node]);
}
else
comp2[nod]=min(comp2[nod],lg1[node]);
}
int cnt=0;
if(comp2[nod]==lg1[nod]&&comp1[nod]!=0)
{
for(int z=0;z<muchii1[nod].size();z++)
{
int i=muchii1[nod][z];
if(i==comp1[nod])
cnt++;
}
for(int z=0;z<muchii2[nod].size();z++)
{
int i=muchii2[nod][z];
if(i==comp1[nod])
cnt++;
}
if(cnt==1)
cout<<comp1[nod]<<' '<<nod<<'\n';
}
}
void dfs1(int nod)
{
use[nod]=1;
nodes.push_back(nod);
for(int z=0;z<muchii1[nod].size();z++)
{
int i=muchii1[nod][z];
if(!use[i])
dfs1(i);
}
}
void dfs2(int nod)
{
use[nod]=1;
nodes.push_back(nod);
for(int z=0;z<muchii2[nod].size();z++)
{
int i=muchii2[nod][z];
if(!use[i])
dfs2(i);
}
}
void dsu_merge1(int a,int b)
{
int c1=comp1[a],c2=comp1[b];
if(lg1[c1]<lg1[c2])
{
swap(c1,c2);
swap(a,b);
}
nodes.clear();
dfs1(b);
for(int i:nodes)
{
comp1[i]=c1;
use[i]=0;
}
lg1[c1]+=lg1[c2];
lg1[c2]=0;
}
void dsu_merge2(int a,int b)
{
int c1=comp2[a],c2=comp2[b];
if(lg2[c1]<lg2[c2])
{
swap(c1,c2);
swap(a,b);
}
nodes.clear();
dfs2(b);
for(int i:nodes)
{
comp2[i]=c1;
use[i]=0;
}
lg2[c1]+=lg2[c2];
lg2[c2]=0;
}
int main()
{
cin>>n>>m;
muchii1.resize(n+1);
muchii2.resize(n+1);
for(int i=1;i<=n;i++)
{
comp1[i]=i;
comp2[i]=i;
lg1[i]=1;
lg2[i]=1;
}
int cnt=0;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
if(comp1[a]!=comp1[b])
{
dsu_merge1(a,b);
muchii1[a].push_back(b);
muchii1[b].push_back(a);
cnt++;
}
else
{
if(comp2[a]!=comp2[b])
{
dsu_merge2(a,b);
muchii2[a].push_back(b);
muchii2[b].push_back(a);
cnt++;
}
}
}
for(int i=1;i<=n;i++)
{
comp1[i]=0;
comp2[i]=0;
lg1[i]=0;
lg2[i]=0;
}
for(int i=1;i<=n;i++)
if(!use[i])
dfs(i);
return 0;
}
Compilation message
pipes.cpp:2: warning: ignoring '#pragma GCC opimize' [-Wunknown-pragmas]
2 | #pragma GCC opimize("O3")
|
pipes.cpp: In function 'void dfs(int)':
pipes.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int z=0;z<muchii1[nod].size();z++)
| ~^~~~~~~~~~~~~~~~~~~~
pipes.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int z=0;z<muchii2[nod].size();z++)
| ~^~~~~~~~~~~~~~~~~~~~
pipes.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int z=0;z<muchii1[nod].size();z++)
| ~^~~~~~~~~~~~~~~~~~~~
pipes.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int z=0;z<muchii2[nod].size();z++)
| ~^~~~~~~~~~~~~~~~~~~~
pipes.cpp: In function 'void dfs1(int)':
pipes.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int z=0;z<muchii1[nod].size();z++)
| ~^~~~~~~~~~~~~~~~~~~~
pipes.cpp: In function 'void dfs2(int)':
pipes.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int z=0;z<muchii2[nod].size();z++)
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
8 ms |
840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
260 ms |
884 KB |
Output is correct |
| 2 |
Correct |
247 ms |
736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
477 ms |
2048 KB |
Output is correct |
| 2 |
Correct |
505 ms |
1512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
729 ms |
4588 KB |
Output is correct |
| 2 |
Correct |
610 ms |
4572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
955 ms |
13284 KB |
Output is correct |
| 2 |
Correct |
827 ms |
9948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1456 ms |
15100 KB |
Output is correct |
| 2 |
Correct |
1450 ms |
11528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2079 ms |
18620 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2488 ms |
18724 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2953 ms |
17732 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
