Pagini recente » Cod sursa (job #2956641) | Cod sursa (job #682302) | Cod sursa (job #731598) | Cod sursa (job #838167) | Cod sursa (job #1276619)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f=fopen("biconex.in","r");
FILE *g=fopen("biconex.out","w");
struct vec
{ int x,y;} st[200005];
int n,m,x,y,viz[100005],l[100005],nv[100005],t[100005],rad,nr,i,nrc,k,p,j,sol[100005];
vector <int> v[100005],c[200005];
void df(int nod)
{
int i,x,y;
viz[nod]=1;
l[nod]=nv[nod];
x=nod;
for(i=0;i<v[nod].size();i++)
if(!viz[v[nod][i]])
{
y=v[nod][i];
k++; st[k].x=x; st[k].y=y;
nv[v[nod][i]]=nv[nod]+1;
t[v[nod][i]]=nod;
if(nod==rad)nr++;
df(v[nod][i]);
if(l[nod]>l[v[nod][i]]) l[nod]=l[v[nod][i]];
if(l[v[nod][i]] >= nv[nod])
{
nrc++;
while(!(st[k].x==x && st[k].y==y))
{
c[nrc].push_back(st[k].x);
c[nrc].push_back(st[k].y);
k--;
}
c[nrc].push_back(st[k].x);
c[nrc].push_back(st[k].y);
k--;
}
}
else
if(v[nod][i]!=t[nod] && l[nod]>nv[v[nod][i]])l[nod]=nv[v[nod][i]];
}
void citire()
{
int i;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(f,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
}
int main()
{
citire();
for(i=1;i<=n;i++)
if(!viz[i])
{
nv[i]=1;
rad=i;
nr=0;
df(i);
}
fprintf(g,"%d\n",nrc);
for(i=1;i<=nrc;i++)
{
sort(c[i].begin(),c[i].end());
p=0;
for(j=0;j<c[i].size();j++)
if (!j || c[i][j]!=c[i][j-1])
{
p++;
sol[p]=c[i][j];
}
for(j=1;j<=p;j++)
fprintf(g,"%d ",sol[j]);
fprintf(g,"\n");
}
fclose(g);
return 0;
}