Pagini recente » Cod sursa (job #2129757) | Cod sursa (job #140984) | Cod sursa (job #128427) | Cod sursa (job #1237839) | Cod sursa (job #574104)
Cod sursa(job #574104)
#include<cstdio>
using namespace std;
FILE *f;
FILE *g;
typedef struct nod
{
int inf;
nod *urm;
} NOD;
typedef NOD *graf[100010];
graf G;
int n,m,nr;
int c[100010],viz[100010];
void citire()
{
f=fopen("dfs.in","r");
fscanf(f,"%d %d",&n,&m);
NOD *p;
int a,b;
for(int i=1;i<=m;i++)
{
fscanf(f,"%d %d",&a,&b);
p=new NOD;
p->inf=b; p->urm=G[a]; G[a]=p;
p=new NOD;
p->inf=a; p->urm=G[b]; G[b]=p;
}
}
void bfs(int s)
{
int pr,ul=pr=1;
c[pr]=s;
viz[s]=1;
while(pr<=ul)
{
NOD *p;
p=G[c[pr]];
while(p)
{
if(!viz[p->inf])
{
c[++ul]=p->inf;viz[p->inf]=1;
}
p=p->urm;
}
pr++;
}
}
void afis()
{
g=fopen("dfs.out","w");
fprintf(g,"%d\n",nr);
fclose(f);
fclose(g);
}
int main()
{
citire();
for(int i=1;i<=n;i++)
if(!viz[i])
{ bfs(i);nr++;};
afis();
return 0;
}