Cod sursa(job #997457)

Utilizator StanAndreiAndrei Stan StanAndrei Data 14 septembrie 2013 10:23:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <list>

#define NMAX 100005
#define MMAX 200005

using namespace std;

list<int> G[NMAX];
bool viz[NMAX];
int N,M,NR;

void read()
{
    scanf("%d %d\n",&N,&M);

    int x,y,i;
    for (i=1;i<=M;i++)
    {
        scanf("%d %d\n",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void dfs(int p)
{
    viz[p]=1;

    list<int>:: iterator it;
    for (it=G[p].begin();it!=G[p].end();it++)
        if (!viz[*it])
            dfs(*it);
}

void solve()
{
    int i;

    for (i=1;i<=N;i++)
        if (!viz[i])
        {
            dfs(i);
            NR++;
        }

    printf("%d\n",NR);
}

int main()
{
    freopen ("dfs.in","r",stdin);
    freopen ("dfs.out","w",stdout);

    read();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}