Cod sursa(job #1947145)

Utilizator gabriel.bjgGabriel b. gabriel.bjg Data 30 martie 2017 19:33:13
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

typedef struct _NOD {
    vector <int> neighbours;
    bool visited = false;
}NOD, *PNOD;

NOD nodes[100005];

int main()
{
    int n, m, i, x, y, cc = 0;
    stack <int> S;

    fin >> n >> m;

    for (i = 0; i < m; i++)
    {
        fin >> x >> y;
        nodes[x].neighbours.push_back(y);
    }

    for (i = 1; i <= n; ++i)
    {
        if (!nodes[i].visited)
        {
            cc++;
            S.push(i);
            while (!S.empty())
            {
                x = S.top();
                S.pop();
                for (int j : nodes[x].neighbours)
                {
                    if (!nodes[j].visited)
                    {
                        S.push(j);
                        nodes[j].visited = true;
                    }
                }
            }
        }
    }

    fout << cc;

    return 0;
}