Cod sursa(job #2352480)

Utilizator MariaPanMaria Pan MariaPan Data 23 februarie 2019 12:44:38
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#define NMAX 100002

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

int n, m, nrc;
vector<int> G[NMAX];
bool uz[NMAX];

void citire();
void DFS(int start);
int main()

{

    int i;

    citire();

    for (i=1; i<=n; i++)

         if (uz[i]==0)

            {DFS(i);

             nrc++;}

    fout<<nrc<<'\n';

    return 0;

}



void citire()

{

    int i, x, y;

    fin>>n>>m;

    for (i=0; i<m; i++)

        {
          //arc
          fin>>x>>y;
          G[x].push_back(y);
        }

}



void DFS(int start)

{

    int i;

    uz[start]=1;

    for (i=0; i<G[start].size(); i++) //nu imi fac probleme ca size se calculeaza constant!
        if (uz[G[start][i]]==0)
           {
            uz[G[start][i]]=1;
            DFS(G[start][i]);
           }

}