#include <iostream>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <iomanip>
#include <vector>
using namespace std;
const int MAXN=1e5+1;
const int LG=17;
int** pa;
int *par,*h,*Up,*par1;
vector<int> ma[MAXN];
int get1(int& a)
{
return ((par1[a]==a)?a:par1[a]=get1(par1[a]));
}
void join1(int a,int b)
{
a=get1(a);
b=get1(b);
if(a!=b)
par1[a]=b;
}
int get(int& a)
{
return ((par[a]==a)?a:par[a]=get(par[a]));
}
bool join(int a,int b)
{
a=get(a);
b=get(b);
if(a!=b)
{
par[a]=b;
return 1;
}
return 0;
}
void dfs(int& x,int& p)
{
// cout<<x<<' '<<p<<endl;
pa[x][0]=p;
for(int j=1;j<LG;j++)
pa[x][j]=pa[pa[x][j-1]][j-1];
h[x]=h[p]+1;
for(auto y:ma[x])
if(y!=p)
dfs(y,x);
}
int lca(int x,int y)
{
if(h[x]>h[y])
swap(x,y);
for(int j=LG-1;j>=0;j--)
if(h[x]<=h[pa[y][j]])
y=pa[y][j];
if(x==y)
return x;
for(int j=LG-1;j>=0;j--)
if(pa[x][j]!=pa[y][j])
{
x=pa[x][j];
y=pa[y][j];
}
return pa[x][0];
}
void solve(int& x,int& p)
{
for(auto y:ma[x])
{
if(y!=p)
{
solve(y,x);
}
}
for(auto y:ma[x])
{
if(y!=p)
{
if(h[Up[x]]>h[Up[y]])
{
Up[x]=Up[y];
}
if(Up[y]==y)
{
cout<<x<<' '<<y<<endl;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
par=new int[n+1];
par1=new int[n+1];
h=new int[n+1];
Up=new int[n+1];
pa=new int*[n+1];
for(int i=1;i<=n;i++)
{
pa[i]=new int[LG];
par[i]=par1[i]=Up[i]=i;
}
for(int i=0;i<m;i++)
{
int x,y;
cin>>x>>y;
if(join(x,y))
{
// cout<<"Tree Edge "<<x<<' '<<y<<endl;
ma[x].push_back(y);
ma[y].push_back(x);
}
else
{
// cout<<"Cycle Edge "<<x<<' '<<y<<endl;
join1(x,y);
}
}
// cout<<"Tree Input:\n";
for(int i=1;i<=n;i++)
if(pa[i][0]==0)
dfs(i,i);
// cout<<"Cycle Input:"<<endl;
for(int y=1;y<=n;y++)
{
int x=get1(y);
// cout<<y<<' '<<x<<endl;
int c=lca(x,y);
if(h[Up[x]]>h[c])
{
Up[x]=c;
}
if(h[Up[y]]>h[c])
{
Up[y]=c;
}
}
// cout<<"Bridge Edges:\n";
for(int i=1;i<=n;i++)
if(pa[i][0]==i)
solve(i,i);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3164 KB |
Output is correct |
2 |
Correct |
5 ms |
3164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
3164 KB |
Output is correct |
2 |
Correct |
68 ms |
3236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
4040 KB |
Output is correct |
2 |
Correct |
131 ms |
4004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
5852 KB |
Output is correct |
2 |
Correct |
162 ms |
6620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
271 ms |
11856 KB |
Output is correct |
2 |
Correct |
253 ms |
12116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
407 ms |
13352 KB |
Output is correct |
2 |
Correct |
395 ms |
13400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
530 ms |
15956 KB |
Output is correct |
2 |
Correct |
523 ms |
15896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
705 ms |
16024 KB |
Output is correct |
2 |
Correct |
669 ms |
15892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
963 ms |
15308 KB |
Output is correct |
2 |
Correct |
755 ms |
16116 KB |
Output is correct |