Pagini recente » Cod sursa (job #735772) | Cod sursa (job #2933828) | Cod sursa (job #2929099) | Cod sursa (job #1234326) | Cod sursa (job #531584)
Cod sursa(job #531584)
#include<stdio.h>
#include<malloc.h>
using namespace std;
typedef struct _nod
{
long int info;
struct _nod *adr;
} nod;
typedef struct
{
struct _nod *cap;
} list;
list A[100001];
long int n;
long int m;
long int C[100001];
char viz[100001];
long int nr = 0;
void citire(void)
{
long int a;
long int b;
FILE *f = fopen("dfs.in","r");
fscanf(f,"%d %d",&n,&m);
for(long int i=1;i<=m;i++)
{
fscanf(f,"%ld %ld",&a,&b);
nod *nou = (nod*)malloc(sizeof(nod));
nou->info = b;
nou->adr = A[a].cap;
A[a].cap = nou;
nod *nou1 = (nod*)malloc(sizeof(nod));
nou1->info = a;
nou1->adr = A[b].cap;
A[b].cap = nou1;
}
fclose(f);
}
void parcurgere(int nod1)
{
long int pi = 1;
long int pf = 1;
viz[nod1] = nr;
C[1] = nod1;
while(pi<=pf)
{
pi++;
nod *q = A[C[pi-1]].cap;
while(q)
{
if(viz[q->info] < 1)
{
C[++pf] = q->info;
viz[q->info] = nr;
}
q = q->adr;
}
}
}
void adaugare(void)
{
for(int i=1;i<=n;i++)
if(viz[i]<1)
{
nr ++;
parcurgere(i);
}
}
int main()
{
FILE *f = fopen("dfs.out","w");
citire();
adaugare();
fprintf(f,"%d",nr);
return 0;
fclose(f);
}