Pagini recente » Cod sursa (job #1991077) | Cod sursa (job #2696291) | Cod sursa (job #218493) | Cod sursa (job #2966751) | Cod sursa (job #172211)
Cod sursa(job #172211)
/*
Cristi Balas,
Facultatea de Matematica si Informatica, Universitatea Bucuresti
cristi8 [at] gmail.com
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct nod // un nod din lista de vecini
{
int vecin;
struct nod *nxt; // next :)
} nod;
#define NMAX 100001
int n;
nod *lv[NMAX]; // lista de vecini a fiecarui nod
char marcat[NMAX];
void adauga_vecin(int cui, int pe_cine)
{
nod *q = malloc(sizeof(nod));
q->vecin = pe_cine;
// q se leaga de inceputul listei de vecini (asa e mai simplu, si nu conteaza ordinea)
q->nxt = lv[cui];
lv[cui] = q;
}
void read_data()
{
int m; // nu e important nr de muchii pt tot programul
int n1, n2; // capetele unei muchii citite
scanf("%d%d", &n, &m);
while(m--)
{
scanf("%d%d", &n1, &n2);
adauga_vecin(n1, n2);
adauga_vecin(n2, n1);
}
}
void df(int nod_id)
{
nod *q;
marcat[nod_id] = 1;
for(q = lv[nod_id]; q; q = q->nxt)
if(!marcat[q->vecin])
df(q->vecin);
}
void solve()
{
int i, count = 0;
for(i = 1; i <= n; i++)
if(!marcat[i])
{
df(i);
count++;
}
printf("%d\n", count);
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
read_data();
solve();
return 0;
}