Pagini recente » Cod sursa (job #1508948) | Cod sursa (job #1356328) | Cod sursa (job #1498598) | Cod sursa (job #2565936) | Cod sursa (job #472839)
Cod sursa(job #472839)
// Parcurgere DFS - componente conexe.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include "stdio.h"
FILE *f=fopen("dfs.in", "r");
FILE *g=fopen("dfs.out", "w");
int n, m, nr;
int viz[100001];
typedef struct nod
{
int x;
struct nod *adr;
};
nod *l[100001];
void read()
{
fscanf(f, "%d%d", &n, &m);
for (int i=1; i<=m; ++i)
{
int x, y;
fscanf(f, "%d%d", &x, &y);
if (l[x]==NULL)
{
l[x]=new nod;
l[x]->x=y;
l[x]->adr=NULL;
}
else
{
nod *p=new nod;
p->x=y;
p->adr=l[x];
l[x]=p;
}
if (l[y]==NULL)
{
l[y]=new nod;
l[y]->x=x;
l[y]->adr=NULL;
}
else
{
nod *q=new nod;
q->x=x;
q->adr=l[y];
l[y]=q;
}
}
}
void dfs(int x)
{
int cr=x;
if (!viz[cr])
{
viz[0]++;
viz[cr]=1;
nod *p=l[cr];
if (l[cr]==NULL) return;
if (!viz[p->x])
dfs(p->x);
while (p->adr!=NULL)
{
if (!viz[p->adr->x])
dfs(p->adr->x);
p=p->adr;
}
}
}
void program()
{
while (viz[0]!=n)
{
int i;
for (i=1; i<=n && viz[i]; ++i);
nr++;
dfs(i);
}
fprintf(g, "%d", nr);
}
int main()
{
read();
program();
return 0;
}