Pagini recente » Cod sursa (job #1923015) | Cod sursa (job #734280) | Cod sursa (job #2328093) | Cod sursa (job #2310932) | Cod sursa (job #1830507)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
FILE *f=fopen("biconex.in","r");
vector <int> lv[200009],lf[200009];
int ni[200009],sus[200009];
stack <int> s;
int n,m,used[200009];
void citire( )
{
fscanf(f,"%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
fscanf(f,"%d%d",&x,&y);
lv[x].push_back(y);
lv[y].push_back(x);
}
}
int k=0,p=0;
void dfs(int nc,int t)
{
used[nc]=1;
ni[nc] = ni[t]+1;
sus[nc] = ni[nc];
vector <int> ::iterator ii;
s.push(nc);
for(ii=lv[nc].begin();ii!=lv[nc].end();ii++)
{
if(t==*ii)
continue ;
if(!used[*ii])
{
dfs(*ii,nc);
sus[nc]=min(sus[nc],sus[*ii]);
if(ni[nc]<=sus[*ii])
{
k++;
while(s.top( )!=nc)
{
lf[k].push_back(s.top());
s.pop();
}
lf[k].push_back(nc);
}
}
else
{
sus[nc]=min(sus[nc],sus[*ii]);
}
}
}
int main()
{
citire( );
dfs(1,0);
FILE *f=fopen("biconex.out","w");
for(int i=1;i<=n;i++)
if(!used[i])
dfs(i,0);
fprintf(f,"%d\n",k);
vector <int> ::iterator ii;
for(int i=1;i<=k;i++)
{for(ii=lf[i].begin();ii!=lf[i].end();ii++)
fprintf(f,"%d ",*ii);
fprintf(f,"\n");
}
return 0;
}