Cod sursa(job #1944546)

Utilizator cyg_Miky2003Dancaescu Mihai cyg_Miky2003 Data 29 martie 2017 10:13:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 100000;

#define WHITE 0

vector<int> G[NMAX + 5];
vector<int> viz;

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 n, m, i, u, v, cnt;
    scanf("%d%d", &n, &m);
    for(int 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);
    DFS(1, 1);
    cnt = 1;
    for(i = 1;i <= n;++i)
    {
      if(viz[i] == WHITE)
      {
        cnt++;
        DFS(i, cnt);
      }
    }
    printf("%d\n", cnt);
    return 0;
}