Cod sursa(job #1944578)

Utilizator alex202Alex Abrudan alex202 Data 29 martie 2017 10:21:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int NMAX=100000;
vector<int>G[NMAX+5];
int n;
vector<int>viz;
#define WHITE 0
void dfs(int u,int cc)
{
    viz[u]=cc;
    for(int j=0; j<(int)G[u].size();j++)
    {
        int v=G[u][j];
        if(viz[v]==WHITE)
        dfs(v,cc);
        
    }
}

int main()
{
    freopen("dfs.in","r",stdin);
    
    freopen("dfs.out","w",stdout);
    int m,i,v,cc=0,u;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
                G[u].push_back(v);
        G[v].push_back(u);
        
    }
    viz.assign(n+1,WHITE);
    for(i=1;i<=n;i++)
    if(viz[i]==WHITE)
    {
        cc++;
        dfs(i,cc);
    }
    printf("%d",cc);
    return 0;
}