Cod sursa(job #1265440)

Utilizator dica69Alexandru Lincan dica69 Data 17 noiembrie 2014 12:34:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>

using namespace std;

struct nod{int x;nod *urm;};
nod *a[100001];
int n,m,use[100001],i,x,y,k;

void add(nod *&p,int b)
{nod *t;
t=new nod;
t->x=b;
t->urm=p;
p=t;
}

void dfs(int b)
{nod *p;
use[b]=1;
for (p=a[b];p;p=p->urm) if (!use[p->x]) dfs(p->x);
}

int main()
{FILE *f1 = fopen("dfs.in","r");
FILE *f2 = fopen("dfs.out","w");
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f1,"%d%d",&x,&y);
add(a[x],y);add(a[y],x);}
for (i=1;i<=n;i++) if(!use[i]) {k++;dfs(i);}
fprintf(f2,"%d",k);
fclose(f1);fclose(f2);
    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.