Cod sursa(job #2465277)

Utilizator ViAlexVisan Alexandru ViAlex Data 29 septembrie 2019 18:44:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

vector<int> arc[100000];
int n,m;
bool passed[100000];


void read()
{
    in>>n>>m;
    int a,b;
    for(int i=0; i<m; i++)
    {
        in>>a>>b;
        arc[a-1].push_back(b-1);
        arc[b-1].push_back(a-1);
    }

}


void dfs(int nod)//numarul de noduri dintr-o componenta
{

    passed[nod]=true;
    for(int k=0; k<arc[nod].size(); k++)
    {
        int vec=arc[nod][k];
        if(!passed[vec])
        {
            dfs(vec);
        }

    }
}

int rezolva()
{
    int rezultat=0;
    for(int i=0; i<n; i++)
    {
        if(!passed[i])//gasim o componenta conexa
        {
            dfs(i);
            rezultat++;
        }
    }
    return rezultat;

}


int main()
{
    read();
    out<<rezolva();
    return 0;
}