Cod sursa(job #1944539)

Utilizator Andrei_Info1Ionescu Andrei Andrei_Info1 Data 29 martie 2017 10:11:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 100000;
vector <int> G[NMAX + 5];
int n;
vector <int> viz;
#define WHITE 0
#define GRAY 1
#define BLACK 2
void DFS(int u, int cc)
{
  viz[u] = cc;
  for(int j=0 ; j<(int)G[u].size() ; j++ )
  {
    int v = G[u][j];
    if(viz[v] == WHITE)
      DFS(v, cc);
  }
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);

    int m, i, u, v, cc = 0;
    scanf("%d%d", &n, &m);
    for(i=1 ; i<=m ; i++)
    {
      scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
    }
    viz.assign(n+1, WHITE);

    for(i=1 ; i<=n ; i++)
      if(viz[i] == WHITE)
      {
        cc++;
        DFS(i,cc);
      }
    printf("%d", cc);

    return 0;
}