Pagini recente » Cod sursa (job #764320) | Cod sursa (job #38425) | Cod sursa (job #2603344) | Cod sursa (job #1609540) | Cod sursa (job #1919265)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#define nmax 100009
using namespace std;
list <int> g[nmax];
list <int> conex[nmax];
int nrc;
int d[nmax],low[nmax],t[nmax];
int time;
int stf[nmax],sts[nmax],vf=-1;
void afisare(int u,int ut){
/*
cout<<"stiva:\n";
for(int i=0;i<=vf;i++)cout<<stf[i]<<' '<<sts[i]<<endl;
cout<<"gata\n";
cout<<u<<' '<<ut<<endl;
*/
nrc++;
int n,nt,numb=0;
do{n=stf[vf];nt=sts[vf];
conex[nrc].push_back(nt);
vf--;numb++;
}while(n!=u || nt!=ut);
if(numb==1)conex[nrc].push_back(n);
}
void dfs(int x){
d[x]=++time;
low[x]=time;
for(list<int>::iterator it=g[x].begin();it!=g[x].end();++it){
int u=*it;
if(d[u]<d[x] && u!=t[x]){
stf[++vf]=u; sts[vf]=x;
}
if(!d[u]){
t[u]=x;
dfs(u);
low[x]=min(low[x],low[u]);
if(low[u]>=d[x]){
afisare(u,x);
}
}else if(u!=t[x]){low[x]=min(low[x],d[u]);}
}
}
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int main(){
int n,m,x,y,i;
fin>>n>>m;
while(m--)
{fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!d[i])
{dfs(i);}
fout<<nrc<<'\n';
for(i=1;i<=nrc;i++)
{for(list<int>::iterator it=conex[i].begin();it!=conex[i].end();it++)
fout<<*it<<' ';
fout<<'\n';}
}