Pagini recente » Cod sursa (job #2508151) | Cod sursa (job #3191316) | Cod sursa (job #2142755) | Cod sursa (job #2308711) | Cod sursa (job #389402)
Cod sursa(job #389402)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define max 100010
using namespace std;
vector<int> g[max],comp[max];
typedef vector<int>::iterator IT;
int n,m,i,j,timp,low[max],ind[max],t[max],stack[max],top,scc;
char s[max];
void add(int v,int w)
{
scc++;
int i,j;
vector<int> aux;
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());
comp[scc].push_back(aux[0]);
for(int i=1; i<aux.size(); i++)
if(aux[i]!=aux[i-1])
comp[scc].push_back(aux[i]);
}
void dfs(int v)
{
s[v]=1;
low[v]=ind[v]=++timp;
for(IT i=g[v].begin(); i!=g[v].end(); ++i)
if(!s[*i])
{
t[*i]=v;
stack[++top]=v;
stack[++top]=*i;
dfs(*i);
low[v]=(low[v]>low[*i]) ? low[*i]:low[v];
if(low[*i]>=ind[v]) add(v,*i);
}
else
if(*i!=t[v])
low[v]=(low[v]>ind[*i]) ? ind[*i]:low[v];
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(; 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",scc);
for(i=1; i<=scc; i++)
{
for(IT j=comp[i].begin(); j!=comp[i].end(); ++j)
printf("%d ",*j);
printf("\n");
}
return 0;
}