Cod sursa(job #3250892)

Utilizator BuciuBuciu Theodor Marian Buciu Data 24 octombrie 2024 08:51:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

struct node
{
    vector<int> next;
    bool vizitat=false;
} v[100001];

void dfs(int n)
{
    v[n].vizitat=true;
    for(auto i:v[n].next)
        if(!v[i].vizitat)
            dfs(i);
}

int n,m;

int main()
{
    f>>n>>m;
    for(int i=0,a,b; i<m; i++)
    {
        f>>a>>b;
        v[a].next.push_back(b);
        v[b].next.push_back(a);
    }
    int s=0;
    for(int i=1; i<=n; i++)
    {
        if(v[i].vizitat)
            continue;
        s++;
        dfs(i);
    }
    g<<s;
}