Pagini recente » Cod sursa (job #3168275) | Cod sursa (job #496293) | Cod sursa (job #1151795) | Cod sursa (job #575701) | Cod sursa (job #2202626)
#include <stdio.h>
struct muchie{
int i;
int j;
};
int n,m,nv[100005],lv[400005],vizitat[100005],nrcomp;
muchie mx[200005];
void schimba(int &a,int &b)
{
int aux;
aux=a; a=b; b=aux;
}
int vecin(int i,int k)
{
if(mx[k].i==i)
return mx[k].j;
return mx[k].i;
}
void dfsc(int i)
{
int j,k;
vizitat[i]=1;
// printf("%d ",i);
for(k=nv[i]+1;k<=nv[i+1];k++)
{
j=vecin(i,lv[k]);
if(vizitat[j]==0)
dfsc(j);
}
}
int main()
{
int i,j,k;
FILE *f,*g;
f=fopen("dfs.in","r");
g=fopen("dfs.out","w");
fscanf(f,"%d%d",&n,&m);
for (k=1;k<=m;k++)
{
fscanf(f,"%d%d",&i,&j);
nv[i]++;nv[j]++;
mx[k].i=i;mx[k].j=j;
}
for(i=2;i<=n;i++)
nv[i]+=nv[i-1];
for(k=1;k<=m;k++)
{
i=mx[k].i;
j=mx[k].j;
lv[nv[i]--]=k;
lv[nv[j]--]=k;
}
nv[n+1]=2*m;
for(i=1;i<=n;i++)
{
if(vizitat[i]==0)
{
nrcomp++;
// printf("\n");
dfsc(i);
}
}
fprintf(g,"%d",nrcomp);
}