Cod sursa(job #1203833)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 1 iulie 2014 13:20:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
using namespace std;
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
int n,m,compon;
int t[100001],nrc,mu;

struct nod {int val;nod *adr;};


nod *prim[100001],*u[100001];

inline void add(int x,int y)
{nod *p;
p=new nod;
p->val=y;
p->adr=0;

if (u[x]==0) {prim[x]=p;}
        else {u[x]->adr=p;}
u[x]=p;
}

inline void dfs(int k)
{nod *p;
p=prim[k];
while (p!=NULL) {if (t[p->val]==0) {t[p->val]=compon;
                                    dfs(p->val);}
                 p=p->adr;}
}

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);
                    add(x,y);
                    add(y,x);
                    }

for (k=1;k<=n;k++) if (t[k]==0)
{t[k]=++compon;
dfs(k);}

fprintf(g,"%d\n",compon);

return 0;
}