Pagini recente » Cod sursa (job #1314271) | Cod sursa (job #291614) | Cod sursa (job #314917) | Cod sursa (job #1797913) | Cod sursa (job #641517)
Cod sursa(job #641517)
#include<fstream>
#include<vector>
using namespace std;
vector <int> v[100100],tmp;
vector <vector <int> > sol;
vector <pair<int,int> > s;
int n,lvl[100100],low[100100];
void afis() {
unsigned int i,j;
ofstream out("biconex.out");
out<<sol.size()<<'\n';
for(i=0;i<sol.size();i++) {
sort(sol[i].begin(),sol[i].end());
sol[i].erase(unique(sol[i].begin(),sol[i].end()),sol[i].end());
for(j=0;j<sol[i].size();j++)
out<<sol[i][j]<<" ";
out<<'\n';
}
out.close();
}
void avem_sol(int nod,int vecin) {
int x,y;
do {
x=s.back().first;
y=s.back().second;
s.pop_back();
tmp.push_back(x);
tmp.push_back(y);
}while(x!=nod||y!=vecin);
sol.push_back(tmp);
tmp.clear();
}
void DFS(int nod,int tata,int level) {
unsigned int i,vecin;
lvl[nod]=low[nod]=level;
for(i=0;i<v[nod].size();i++) {
vecin=v[nod][i];
if(vecin==tata) continue;
if(!lvl[vecin]) {
s.push_back(pair<int,int>(nod,vecin));
DFS(vecin,nod,level+1);
low[nod]=min(low[nod],low[vecin]);
if(low[vecin]>=lvl[nod])
avem_sol(nod,vecin);
}
else
low[nod]=min(low[nod],lvl[vecin]);
}
}
void citire() {
int i,m,x,y;
ifstream in("biconex.in");
in>>n>>m;
for(i=0;i<m;i++) {
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
in.close();
}
int main() {
citire();
DFS(1,0,1);
afis();
return 0;
}