Pagini recente » Cod sursa (job #1557750) | Istoria paginii runda/iconcurs4 | Cod sursa (job #2801933) | Cod sursa (job #1343820) | Cod sursa (job #1692232)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define DX 200100
using namespace std;
fstream fin("biconex.in",ios::in),fout("biconex.out",ios::out);
int nr[DX],low[DX],art[DX],ap[DX],ind=0,n,m,nrc=0;
vector <int> v[DX];
vector <int> r[DX];
stack <pair<int,int> > st;
void citire()
{
int a,b,i;
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);}
for(i=1;i<=n;i++) low[i]=nr[i]=-1;
}
void scrie(int nod,int x)
{
int a,b;
nrc++;
//cout<<"comp conexa: "<<nrc<<"\n";
do
{
a=st.top().first; b=st.top().second;
if(ap[a]!=nrc) r[nrc].push_back(a);
if(ap[b]!=nrc) r[nrc].push_back(b);
ap[a]=ap[b]=nrc;
//cout<<a<<" "<<b<<"\n";
st.pop();
}while(!st.empty() && (a!=nod || b!=x));
}
void biconex(int nod,int parinte)
{
int i,x;
nr[nod]=low[nod]=++ind;
for(i=0;i<v[nod].size();i++)
{
x=v[nod][i];
if(x!=parinte)
{
if(nr[x]<nr[nod])
{
st.push(make_pair(nod,x));
}
if(low[x]==-1)
{
biconex(x,nod);
low[nod]=min(low[nod],low[x]);
if(low[x]>=nr[nod]) //punct de articulatie
{
scrie(nod,x);
art[nod]=1;
}
}
else
{
low[nod]=min(low[nod],nr[x]);
}
}
}
}
int main()
{
citire();
biconex(1,-1);
fout<<nrc<<"\n";
for(int i=1;i<=nrc;i++)
{
for(int j=0;j<r[i].size();j++)
fout<<r[i][j]<<" ";
fout<<"\n";
}
}