Cod sursa(job #1131338)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 28 februarie 2014 19:28:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#include <vector>
#include <bitset>
#define Nmax 100009
using namespace std;

int N,M,sol;
bitset < Nmax > viz;
vector < int > G[Nmax];

inline void dfs(int node)
{
     viz[node]=1;
     for(vector<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);
     for(int i=1;i<=M;++i)
     {
          int x,y;
          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])++sol,dfs(i);
     printf("%d\n",sol);
     return 0;
}