Cod sursa(job #1203801)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 1 iulie 2014 12:32:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
using namespace std;
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
int n,m,compon;
int v[2][1000005],prim[100001];

int p[100001],c[500000],nrc,mu;

inline void creeaza(int x,int y,int i)
{v[0][i]=y;
v[1][i]=prim[x];
prim[x]=i;



}

int main()
{int i,j,s,x,y,k;
fscanf(f,"%d %d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f,"%d %d",&x,&y);
                     creeaza(x,y,++mu);
                     creeaza(y,x,++mu);
                     }
for (k=1;k<=n;k++) if (p[k]==0)
{p[k]=++compon;
nrc=1;
c[nrc]=k;
i=1;
while (i<=nrc) {j=prim[c[i]];
                while (j!=0) {if (p[v[0][j]]==0) {p[v[0][j]]=compon;
                                                  c[++nrc]=v[0][j];
                                                  }
                              j=v[1][j];
                              }
                i++;
                }
}
fprintf(g,"%d\n",compon);
return 0;
}