Cod sursa(job #1108266)

Utilizator zaharia_horiaZaharia Horia zaharia_horia Data 15 februarie 2014 15:27:08
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<vector>
#include<cstdio>

using namespace std;

const int  nmax=100003;

vector <int> g[nmax+1];
bool v[nmax+1];

 void dfs(int a)
 {

     v[a] = 1;
     for(int i = 0; i<(int)g[a].size(); i++)
      {   if(v[g[a][i]]==0)
                dfs(g[a][i]);
      }
}

int main(){

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

    int n, x, y, m,nr=0;


        scanf("%d%d", &n, &m);

        for(;m>=0;m--){
            scanf("%d%d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }


    for(int i=1;i<=n;i++)
    {
        if(v[i]==0)
            {
                dfs(i);
                nr++;
            }
    }

    printf("%d",nr);
}