Cod sursa(job #1193569)

Utilizator c0rn1Goran Cornel c0rn1 Data 1 iunie 2014 00:12:06
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#define add push_back

using namespace std;
vector<int> v[100005];
bitset<100005> viz;
int n, m;

void Citire()
{
   int i, x, y;
   scanf("%d %d", &n, &m);
   for (i=0; i<m; i++)
   {
      scanf("%d %d", &x, &y);
      if (x!=y)
         v[x].add(y);
   }
}

void dfs(int nod)
{
   if (!viz[nod])
   {
      viz[nod]=1;
      for (vector<int>::iterator it=v[nod].begin(); it!=v[nod].end(); ++it)
         dfs(*it);
   }
}

int main()
{
   freopen("dfs.in", "r", stdin);
   freopen("dfs.out", "w", stdout);
   int i, nr=0;
   Citire();
   for (i=1; i<=n; i++)
      if (!viz[i])
      {
         nr++;
         dfs(i);
      }
   printf("%d", nr);
   return 0;
}