Pagini recente » Cod sursa (job #3313629) | Cod sursa (job #2794055) | Cod sursa (job #3336643) | Borderou de evaluare (job #1536357) | Cod sursa (job #3344641)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int N=1e5+5,M=2e5+5;
struct elem
{
int x,y;
};
struct nod
{
int depth,low;
vector<int> edge;
nod(): depth(0),low(0) {}
};
int n,m,i,j,x,y,sz,tot;
set<int> comp[M];
elem s[M];
nod v[M];
void read()
{
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>x>>y;
v[x].edge.push_back(y);
v[y].edge.push_back(x);
}
}
void add_bcc(int x,int y)
{
tot++;
do
{
--sz;
if(sz<0) break;
comp[tot].insert(s[sz].x);
comp[tot].insert(s[sz].y);
}while(s[sz].x!=x || s[sz].y!=y);
}
void dfs(int x,int par)
{
static int time=0;
v[x].depth=v[x].low=++time;
for(auto y:v[x].edge)
{
if(!v[y].depth)
{
s[sz++]={x,y};
dfs(y,x);
v[x].low=min(v[x].low,v[y].low);
if(v[y].low>v[x].depth)
{
cout<<x<<' '<<y<<endl;
///bridge
}
if(v[y].low>=v[x].depth)
{
add_bcc(x,y);
}
}
else if(y!=par)
{
s[sz++]={x,y};
v[x].low=min(v[x].low,v[y].depth);
}
}
}
void print()
{
fout<<tot<<'\n';
for(int i=1;i<=tot;++i)
{
for(auto it=comp[i].begin();it!=comp[i].end();++it)
fout<<(*it)<<' ';
fout<<'\n';
}
}
int main()
{
read();
dfs(1,0);
print();
return 0;
}