Cod sursa(job #2179296)

Utilizator cezinatorCezar D cezinator Data 20 martie 2018 09:04:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <set>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
set <int> v[100005];
int N,M,X,Y,k=1;
bool viz[100005];
void DFS(int x, int y)
{
    viz[x]=y;
    for(set<int>::iterator it=v[x].begin();it!=v[x].end();it++)
    {
        if(!viz[*it]){DFS(*it,y);}
    }
}
int main()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>X>>Y;
        v[X].insert(Y);
        v[Y].insert(X);
    }
    for(int i=1;i<=N;i++)
    {
        if(viz[i]==0) {DFS(i,k);k++;}
    }
    fout<<k-1;
    return 0;
}