Cod sursa(job #1754264)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 7 septembrie 2016 19:44:05
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>

std::vector <int> v[100001];
bool vis[100001];

void
dfs(int node)
{
    vis[node] = true;

    for (int i = 0; i < (int)v[node].size(); ++i)
    {
        if (not vis[v[node][i]])
        {
            dfs(v[node][i]);
        }
    }
}

int main()
{
    int n;
    int m;
    int counter;
    int x;
    int y;

    std::ifstream mama("dfs.in");
    std::ofstream tata("dfs.out");

    mama >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        mama >> x >> y;

        v[x].push_back(y);
    }

    counter = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (not vis[i])
        {
            dfs(i);
            ++counter;
        }
    }

    tata << counter;

    return 0;
}