Cod sursa(job #507308)

Utilizator chrissBota Cristian chriss Data 5 decembrie 2010 19:11:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>

int n, m, viz[1000005], cnt;

struct nod
{
    int info;
    nod *next;
};
nod *L[100001];

void add(nod *&cap, int info)
{
    nod *p = new nod;
    p->info=info;
    p->next=cap;
    cap=p;
}
void citire()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d",&x,&y);
        add(L[x],y);
        add(L[y],x);
    }
}
void DF(int nd)
{
	viz[nd] = 1;
	for(nod *p = L[nd]; p; p=p->next)
        if (!viz[p->info])
            DF(p->info);
}
int main()
{
    citire();
	for (int i = 1; i <= n; i++)
        if (!viz[i])
        {
            cnt++;
            DF(i);
        }
	printf("%d\n",cnt);
	return 0;
}