Cod sursa(job #2424540)

Utilizator MikeVMihai Vasilescu MikeV Data 23 mai 2019 10:59:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 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;
    for(int i=0;i<n;i++)
    {
        if(eticheta[i]==0)
            DFS(i,g,eticheta,comp);
        comp++;
    }
	
	int nr = 0;
    for(int i=0;i<n;i++)
    {
        if(eticheta[i] == 1)
        	nr++;
    }
    out << nr;
    
    return 0;
}