Cod sursa(job #392793)

Utilizator hulparuadrianhulparu adrian hulparuadrian Data 8 februarie 2010 12:14:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
// parcurgere DFS - componente conexe
#include<stdio.h>
#include<vector>
#define SIZE 100010
#define pb push_back
using namespace std;

vector <int> graf[SIZE];
int N, M, viz[SIZE], sol;

void dfs(int u)
{
     viz[u] = 1;
     for(int j = 0; j < graf[u].size(); j++)
     if (!viz[graf[u][j]]) dfs(graf[u][j]);     
     }

int main()
{
    int i, x, y;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d", &N, &M);
    for(i = 1; i <= M; i++)
    {
          scanf("%d %d", &x, &y);
          graf[x].pb(y);
          graf[y].pb(x);
          }
    
    for(i = 1; i <= N; i++)
          if (!viz[i]) {sol++; dfs(i);}
          
    printf("%d \n", sol);        
    
    fclose(stdin);    
    fclose(stdout);      
    return 0;
    }