Pagini recente » Cod sursa (job #544879) | Cod sursa (job #1527433) | Cod sursa (job #620396) | Cod sursa (job #1028503) | Cod sursa (job #382134)
Cod sursa(job #382134)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define max 100010
using namespace std;
struct lista
{
int nod;
lista *next;
};
int min(int a,int b)
{
if(a>b) return b;
return a;
}
lista *g[max],*sol[max],*p;
int n,m,i,j,preord[max],nivmin[max],t[max],stack[max*2],top,timp,comp;
char s[max];
vector<int> compc[max];
void push(lista *&i,int j)
{
lista *p=new lista;
p->nod=j;
p->next=i;
i=p;
}
void add(int v,int w)
{
int i,j;
vector<int> aux;
comp++;
do
{
j=stack[top--]; i=stack[top--];
aux.push_back(i);
aux.push_back(j);
}
while(i!=v || j!=w);
sort(aux.begin(),aux.end());
compc[comp].push_back(aux[0]);
for(i=1; i<aux.size(); i++)
if(aux[i]!=aux[i-1])
compc[comp].push_back(aux[i]);
}
void dfs(int v)
{
int w;
s[v]=1;
preord[v]=nivmin[v]=++timp;
for(lista *p=g[v]; p!=NULL; p=p->next)
{
w=p->nod;
if(!s[w])
{
stack[++top]=v;
stack[++top]=w;
dfs(w);
if(nivmin[w]>=preord[v]) add(v,w);
nivmin[v]=min(nivmin[v],nivmin[w]);
}
else
nivmin[v]=min(nivmin[v],preord[w]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(; m>0; m--)
{
scanf("%d%d",&i,&j);
push(g[i],j);
push(g[j],i);
}
for(i=1; i<=n; i++)
if(!s[i])
{
timp=0;
dfs(i);
}
printf("%d\n",comp);
for(i=1; i<=comp; i++)
{
for(j=0; j<compc[i].size(); j++)
printf("%d ",compc[i][j]);
printf("\n");
}
return 0;
}