Cod sursa(job #2558718)

Utilizator Virlan_CristianVirlan Cristian Alexandru Virlan_Cristian Data 26 februarie 2020 19:17:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m;
vector<int>muchie[NMAX];
void read()
{
    fin>>n>>m;
    while(m)
    {
        int x,y;
        fin>>x>>y;
        muchie[x].push_back(y);
        muchie[y].push_back(x);
        m--;
    }
}
bool sel[NMAX];
void DFS(int i)
{
    sel[i]=true;
    for(size_t j=0;j<muchie[i].size();j++)
        if(!sel[muchie[i][j]])DFS(muchie[i][j]);
}
int main()
{
    read();
    int nr=0;
    for(int i=1;i<=n;i++)
        if(!sel[i])
    {
        DFS(i);
        nr++;
    }
    fout<<nr;
    return 0;
}