Cod sursa(job #1503578)

Utilizator grimmerFlorescu Luca grimmer Data 16 octombrie 2015 15:13:05
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX=100;
vector<int>G[NMAX+5]; /// vector de containere(aka vectori) vide
bool viz[NMAX+5];
void dfs(int u, int cc){
    int v;
    viz[u]=cc;
    for(int i=0;i<(int)G[u].size();++i){
        v=G[u][i];
        if(viz[v]==0){
            dfs(v,cc);
        }
    }
}
int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    int u,v,i,n,m,componente;
    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);
    }
    /// nr de componente conexe
    componente=0;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
            dfs(i,++componente);
    }
    printf("%d\n",componente);
    return 0;
}