Cod sursa(job #1545937)

Utilizator fromzerotoheroFROM ZERO fromzerotohero Data 7 decembrie 2015 14:22:26
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>

#define nmax 100001

using namespace std;

int n, m;
int x, y, rez;
bool viz[nmax];
vector <int> G[nmax];

void dfs(int nod)
{
    viz[nod] = true;
    
    for (int i = 0; i < G[nod].size(); i++)
        if (!viz[G[nod][i]])
            dfs(G[nod][i]);
}

int main()
{
    
    ifstream fi("dfs.in");
    ofstream fo("dfs.out");
    
    fi >> n >> m;
    
    for (int i = 1; i <= m; i++)
        fi >> x >> y,
        G[x].push_back(y);
    
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i),
            rez++;
    
    fo << rez << "\n";
    
    fi.close();
    fo.close();
    
    return 0;
}