Pagini recente » Cod sursa (job #1708828) | Cod sursa (job #2281018) | Cod sursa (job #1881502) | Cod sursa (job #2977550) | Cod sursa (job #868907)
Cod sursa(job #868907)
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
#define nmax 100100
using namespace std;
stack < pair<int,int> > St;
vector <int> G[nmax],Answer[nmax];
int N,NrCb,Nivel[nmax],Low[nmax];
void Add(int A,int B) {
int x,y;
++NrCb;
do {
x=St.top().first;
y=St.top().second;
Answer[NrCb].push_back(y);
St.pop();
}while(A!=x && B!=y);
Answer[NrCb].push_back(x);
}
void DFS(int Nod,int Tata) {
int i,Vecin;
Nivel[Nod]=Nivel[Tata]+1;
Low[Nod]=Nivel[Nod];
for(i=0;i<G[Nod].size();i++) {
if((Vecin=G[Nod][i])==Tata)
continue;
if(!Nivel[Vecin]) {
St.push(make_pair(Nod,Vecin));
DFS(Vecin,Nod);
if(Low[Vecin]>=Nivel[Nod])
Add(Nod,Vecin);
}
Low[Nod]=min(Low[Nod],Low[Vecin]);
}
}
void Read() {
int x,y,M;
ifstream in("biconex.in");
in>>N>>M;
while(M--) {
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
in.close();
}
void Write() {
int i,j;
ofstream out("biconex.out");
out<<NrCb<<'\n';
for(i=1;i<=NrCb;i++) {
for(j=0;j<Answer[i].size();j++)
out<<Answer[i][j]<<' ';
out<<'\n';
}
out.close();
}
int main() {
Read();
DFS(1,0);
Write();
return 0;
}