Pagini recente » Cod sursa (job #3256392) | Cod sursa (job #1272577) | Cod sursa (job #800700) | Cod sursa (job #58795) | Cod sursa (job #1203833)
#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;
}