Cod sursa(job #1192610)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 29 mai 2014 13:31:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <vector>
#define pb push_back
#define LL long long
#define Nmax 100010

using namespace std;

vector <LL> g[Nmax];
LL n,m,i,nrc,x,y;
bool sel[Nmax];

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

void dfs(int x)
 {
     int i;
     sel[x]=true;
     for (i=0;i<g[x].size();++i)
      if (!sel[g[x][i]])
       dfs(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])
      {
          nrc++;
          dfs(i);
      }

    printf("%lld\n", nrc);

    return 0;
}