Cod sursa(job #1127787)

Utilizator Sirius2001Happy Birthday Sirius2001 Data 27 februarie 2014 13:50:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
/*
    Keep It Simple!
*/

#include<stdio.h>
#include<list>

#define MaxN 100005

using namespace std;

list<int> G[MaxN];
int n,m,cnt;
bool viz[MaxN];

void DFS(int node)
{
   viz[node] = 1;

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


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

   scanf("%d%d",&n,&m);

   int x,y;

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

    for(int i=1;i<=n;i++)
    {
       if(!viz[i])
       {
         cnt++; DFS(i);
       }
    }

    printf("%d",cnt);
}