Pagini recente » Profil msandupo | Cod sursa (job #3152244) | Cod sursa (job #246944) | Cod sursa (job #3223417) | Cod sursa (job #1167890)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define DN 300005
#define x first
#define y second
using namespace std;
typedef pair<int,int> per;
typedef vector<int>::iterator it;
int low[DN],dfn[DN],cont;
vector <vector <int> > sol;
vector<int> gr[DN];
stack <pair <int, int> > stiva;
void afis(int x,int y) {
int a,b;
vector <int> cc;
do {
a=stiva.top().x;
b=stiva.top().y;
stiva.pop();
cc.push_back(a);
cc.push_back(b);
}while (a!=x || b!=y);
sol.push_back(cc);
}
void biconex(int n,int fn, int nr) {
dfn[n]=low[n]=nr;
for(it i=gr[n].begin(); i!=gr[n].end(); ++i) {
if(*i==fn) continue;
if(dfn[*i]==-1) {//nu a fost viz
stiva.push(make_pair(n,*i));
biconex(*i,n,nr+1);
low[n]=min(low[n],low[*i]);
if(low[*i]>=dfn[n])
++cont,afis(n,*i);
}
else low[n] = min(low[n], dfn[*i]);
}
}
int main()
{
int i,x,y,n,m;
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>n>>m;
for(i=1; i<=m; i++) {
f>>x>>y;
gr[x].push_back(y);
gr[y].push_back(x);
}
for(int i=0; i<=n; ++i) dfn[i]=-1;
biconex(1,0,0);
g<<cont<<'\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 (size_t j = 0; j < sol[i].size(); ++ j)
g<<sol[i][j]<<' ';
g<<'\n';
}
return 0;
}