Pagini recente » Cod sursa (job #2021754) | Cod sursa (job #3204178) | Cod sursa (job #2413631) | Cod sursa (job #1125877) | Cod sursa (job #382136)
Cod sursa(job #382136)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define max 100010
using namespace std;
int n,m,i,j,preord[max],nivmin[max],stack[max*2],top,timp,comp;
char s[max];
vector<int> compc[max],g[max];
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 i;
s[v]=1;
preord[v]=nivmin[v]=++timp;
for(i=0; i<g[v].size(); i++)
{
if(!s[g[v][i]])
{
stack[++top]=v;
stack[++top]=g[v][i];
dfs(g[v][i]);
if(nivmin[g[v][i]]>=preord[v]) add(v,g[v][i]);
nivmin[v]=min(nivmin[v],nivmin[g[v][i]]);
}
else
nivmin[v]=min(nivmin[v],preord[g[v][i]]);
}
}
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);
g[i].push_back(j);
g[j].push_back(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;
}