Pagini recente » Cod sursa (job #2633022) | Cod sursa (job #469315)
Cod sursa(job #469315)
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#define DN 100005
using namespace std;
int low[DN],dfn[DN],cont;
vector <vector <int> > sol;
stack <pair <int, int> > stiva;
struct nod {
int x;
nod *urm;
} *v[DN];
void adaugare(int x,int y) {
nod *p;
p=new nod;
p->x=y;
p->urm=v[x];
v[x]=p;
}
void afis(int x,int y) {
int a,b;
vector <int> componenta;
do {
a=stiva.top().first;
b=stiva.top().second;
stiva.pop();
componenta.push_back(a);
componenta.push_back(b);
}while (a!=x || b!=y);
sol.push_back(componenta);
}
void biconex(int n,int fn, int nr) {
nod *p;
dfn[n]=low[n]=nr;
for(p=v[n];p!=NULL; p=p->urm) {
if(p->x==fn) continue;
if(dfn[p->x]==-1) {//nu a fost viz
stiva.push(make_pair(n,p->x));
biconex(p->x,n,nr+1);
low[n]=min(low[n],low[p->x]);
if(low[p->x]>=dfn[n])
++cont,afis(n,p->x);
}
else low[n] = min(low[n], dfn[p->x]);
}
}
void afisare(int n) {
nod *p;
int k;
for(k=1; k<=n; k++) {
p=v[k];
printf("%d:",k);
while(p) {
printf("%d ",p->x);
p=p->urm;
}
printf("\n");
}
}
int main()
{
int i,x,y,n,m;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
for(i=1; i<=m; i++) {
scanf("%d %d",&x,&y);
adaugare(x,y);
adaugare(y,x);
}
//afisare(n);
memset(dfn,-1,sizeof(dfn));
biconex(1,0,0);
printf("%d\n",cont);
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)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}