Pagini recente » Cod sursa (job #2447210) | Cod sursa (job #979593) | Cod sursa (job #904357) | Cod sursa (job #2743959) | Cod sursa (job #2564180)
#include <fstream>
#include <vector>
#define NMAX 100002
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
struct muchie
{
int x,y;
} aux;
vector <int> v[NMAX],rez[NMAX];
vector<muchie> stiva;
int tata[NMAX],disc[NMAX],low[NMAX],t,nrbiconex;
void dfs(int nod)
{
disc[nod]=low[nod]=++t;
for(vector<int>::iterator it=v[nod].begin(); it!=v[nod].end(); it++)
{
int urm=*it;
if(!disc[urm])
{
tata[urm]=nod;
aux.x=nod;
aux.y=urm;
stiva.push_back(aux);
dfs(urm);
low[nod]=min(low[nod],low[urm]);
if(disc[nod]<=low[urm])
{
nrbiconex++;
rez[nrbiconex].push_back(stiva.back().y);
while(stiva.back().x!=nod)
{
rez[nrbiconex].push_back(stiva.back().x);
stiva.pop_back();
}
rez[nrbiconex].push_back(nod);
stiva.pop_back();
}
}
else if(urm!=tata[nod])
low[nod]=min(low[nod],disc[urm]);
}
}
int main()
{
int i,x,y,n,m;
cin>>n>>m;
for(i=1; i<=m; i++)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1; i<=n; i++)
{
if(!disc[i])
{
t=0;
dfs(i);
}
}
cout<<nrbiconex<<'\n';
for(i=1; i<=nrbiconex; i++)
{
for(vector<int>::iterator it=rez[i].begin(); it!=rez[i].end(); it++)
cout<<*it<<' ';
cout<<'\n';
}
return 0;
}