Cod sursa(job #2007429)

Utilizator Andrei2000Andrei Mihailescu Andrei2000 Data 2 august 2017 21:06:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <bits/stdc++.h>
#define nmax 100002
using namespace std;

ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

vector<int> G[nmax];
int N,M,V[nmax];

void DFS(int nod, int nr){
    V[nod]=nr;
    for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
        if(V[*it]==-1)DFS(*it,nr);
}

int main()
{
    int a,b,n=0;
    fin>>N>>M;
    for(int i=1;i<=M;++i){
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    memset(V,-1,sizeof(V));
    for(int i=1;i<=N;++i)
        if(V[i]==-1)DFS(i,++n);
    fout<<n<<endl;
    return 0;
}