Cod sursa(job #2785369)

Utilizator newagear2Dragan Iulian newagear2 Data 18 octombrie 2021 17:00:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <vector>
#include <fstream>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m;
vector<int> muchii[100005];
bool viz[100005];
void Citire(){
    for(int i=0;i<m;i++){
        int locA, locB;
        fin>>locA>>locB;
        muchii[locA].push_back(locB);
        muchii[locB].push_back(locA);
    }
}
void DFS(int x){
    viz[x]=true;
    for(auto it = muchii[x].begin(); it!=muchii[x].end();it++){
        if(!viz[*it])DFS(*it);
    }
}
int main()
{
    fin>>n>>m;
    Citire();
    {
        int locIterator=n, locCounter=0;
        while(locIterator){
            if(!viz[locIterator]){
                DFS(locIterator);
                locCounter++;
            }
            locIterator--;
        }
        fout<<locCounter;
    }
    return 0;
}