Pagini recente » Cod sursa (job #370772) | Cod sursa (job #2094620) | Cod sursa (job #917502) | Cod sursa (job #1540364) | Cod sursa (job #1746061)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,v[100001],low[100001],nrb,i,vfS,nr;
vector<vector<int>>sol;
int Min(int a,int b){
if (a<b) return a;
return b;
}
struct nod{
int inf;
nod *urm;
}*L[100001];
struct muchie{
int f,t;
}S[100001];
void adaugsf(nod *&vf,int val){
nod *q;
q=new nod;
q->inf=val;
q->urm=vf;
vf=q;
}
void cit(){
int a,b;
fin>>n>>m;
for (i=1;i<=n;i++)
L[i]=0;
for (i=1;i<=m;i++){
fin>>a>>b;
adaugsf(L[a],b);
adaugsf(L[b],a);
}
fin.close();
}
void actualizare(int nod,int t){
vector<int>aux;
muchie i;
nrb++;
do{
i=S[vfS];
aux.push_back(i.t);aux.push_back(i.f);
vfS--;
}while(i.t!=t || i.f!=nod);
sol.push_back(aux);
}
void DFS(int nd,int t){
nod *q;
nr++;
v[nd]=nr;low[nd]=nr;
q=L[nd];
while(q!=0){
if (q->inf!=t)
if (v[q->inf]==-1){
vfS++;
S[vfS].f=q->inf;S[vfS].t=nd;
DFS(q->inf,nd);
low[nd]=Min(low[nd],low[q->inf]);
if (low[q->inf]>=v[nd]) actualizare(q->inf,nd);
}
else
low[nd]=Min(low[nd],v[q->inf]);
q=q->urm;
}
}
int main(){
cit();
S[0].f=1;S[0].t=-1;vfS=0;
for (i=1;i<=n;i++){
v[i]=low[i]=-1;
}
DFS(1,-1);
fout<<sol.size()<<'\n';
size_t l,j;
for (l=0;l<sol.size();l++){
sort(sol[l].begin(),sol[l].end());
sol[l].erase(unique(sol[l].begin(),sol[l].end()),sol[l].end());
for (j=0;j<sol[l].size();j++)
fout<<sol[l][j]<<" ";
fout<<'\n';
}
fout.close();
return 0;
}