Pagini recente » Cod sursa (job #1657514) | Cod sursa (job #848675) | Cod sursa (job #2263044) | Cod sursa (job #210439) | Cod sursa (job #335433)
Cod sursa(job #335433)
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
vector <int> v[100000];
vector <int> componente[100000];
stack < pair <int,int> > s;
int nc=0,viz[100000],df[100000],timp=0,jos[100000];
int min(int a,int b)
{
if(a<b)
return a;
return b;
}
void scoate(int x,int y)
{
int xx,yy;
do
{
xx=s.top().first;
yy=s.top().second;
s.pop();
componente[nc].push_back(xx);
componente[nc].push_back(yy);
}
while(xx!=x || yy!=y);
nc++;
}
void biconex(int rad,int tata)
{
int i,nod;
jos[rad]=timp;
df[rad]=timp;
timp++;
for(i=0;i<(int) v[rad].size();i++)
{
nod=v[rad][i];
if(nod!=tata && df[nod]<df[rad])
s.push(make_pair(rad,nod));
if(df[nod]==-1)
{
biconex(nod,rad);
jos[rad]=min(jos[rad],jos[nod]);
if(jos[nod]>=df[rad])
scoate(rad,nod);
}
else if(nod!=tata)
jos[rad]=min(jos[rad],df[nod]);
}
}
int main()
{
int n,m,a,b,i,j;
FILE *f=fopen("biconex.in","r");
fscanf(f,"%i%i\n",&n,&m);
for(i=0;i<m;i++)
{
fscanf(f,"%i%i\n",&a,&b);
v[a-1].push_back(b-1);
v[b-1].push_back(a-1);
}
fclose(f);
f=fopen("biconex.out","w");
for(i=0;i<n;i++)
df[i]=-1;
biconex(0,-1);
fprintf(f,"%i\n",nc);
for(i=0;i<nc;i++)
{
for(j=0;j<(int) componente[i].size();j++)
viz[componente[i][j]]=0;
for(j=0;j<(int) componente[i].size();j++)
{
if(viz[componente[i][j]]==0)
{
viz[componente[i][j]]=1;
fprintf(f,"%i ",componente[i][j]+1);
}
}
fprintf(f,"%s","\n");
}
fclose(f);
return 0;
}