Cod sursa(job #1141958)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 13 martie 2014 12:30:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>
#define pb push_back

using namespace std;

vector <long long> g[100010];
long long i,n,m,j,nr,x,y;
bool sel[100010];

void load()
 {
     scanf("%lld %lld", &n, &m);
     for (i=1;i<=m;++i)
      {
          scanf("%lld %lld",&x, &y);
          g[x].pb(y);
          g[y].pb(x);
      }
 }

void df(int x)
 {
     int i;
     sel[x]=true;
     for (i=0;i<g[x].size();++i)
      if (!sel[g[x][i]])
         df(g[x][i]);
 }

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

    load();

    for (i=1;i<=n;++i)
     if (!sel[i])
       {
           nr++;
           df(i);
       }

    printf("%lld", nr);

    return 0;
}