Cod sursa(job #2254939)

Utilizator KriSSu09Cristian Serban KriSSu09 Data 6 octombrie 2018 11:17:53
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>

using namespace std;

bool viz[100000];
vector <int> G[100000];

void DFS(int x)
{
    viz[x]=1;
    for (int i=0;i<G[x].size();i++) {
        if (!viz[G[x][i]]) DFS(G[x][i]);
    }
}

int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int N,M,nrcomp=0;
    f>>N>>M;
    for (int i=0;i<M;i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
    }
    for (int i=1;i<=N;i++)
    {
        if (!viz[i]) {
            nrcomp++;
            DFS(i);
        }
    }
    g<<nrcomp;
    return 0;
}