Cod sursa(job #2377076)

Utilizator cezinatorCezar D cezinator Data 8 martie 2019 21:30:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector <int> v[100005];
int N,M,X,Y,comp_conex[100005],c;
void DFS(int n, int contor)
{
    comp_conex[n]=contor;
    for(vector<int> :: iterator it=v[n].begin();it!=v[n].end();it++)
    {
        if(comp_conex[*it]==0) DFS((*it),contor);
    }
}
int main()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>X>>Y;
        v[X].push_back(Y);
        v[Y].push_back(X);
    }
    c=0;
    for(int i=1;i<=N;i++)
    {
        if (comp_conex[i]==0) {c++;DFS(i,c);}
    }
    fout<<c;
    return 0;
}