Cod sursa(job #2424552)

Utilizator MikeVMihai Vasilescu MikeV Data 23 mai 2019 11:19:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

void DFS(int node, vector<vector<int>> &g, vector<int> &eticheta, int comp)
{
    eticheta[node]=comp;
    for(auto vecin : g[node]) ///for(i=0;i<g[node].size();i++)  int vecin = g[node][1];
        if(eticheta[vecin]==0)
            DFS(vecin, g, eticheta, comp);
}

int main()
{
	ifstream in("dfs.in");
	ofstream out("dfs.out");
	
    int n, m;
    in>>n;
    in>>m;
    vector<vector<int>> g(n);
    for(int i=0;i<m;i++)
    {
        int a, b;
        in>>a;
        in>>b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> eticheta(n,0);
    int comp = 1, nr = 0;
    for(int i=0;i<n;i++)
    {
        if(eticheta[i]==0)
        {
        	DFS(i,g,eticheta,comp);
        	nr++;
        }
        comp++;
    }
    
    out << nr;
    
    return 0;
}