Cod sursa(job #2520446)

Utilizator noemi_pz4Penzes Noemi noemi_pz4 Data 9 ianuarie 2020 14:10:52
Problema Parcurgere DFS - componente conexe Scor 75
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
    vector<int> adj[100000];
    bool vizitat[100000];

    fstream f("dfs.in");
    int N,M;

    void dfs(int nod)
    {   vizitat[nod]=true;
        int i;
        for(i=0; i<adj[nod].size(); i++)
         {if(vizitat[adj[nod][i]]==false) {
                                            dfs(adj[nod][i]);
                                          }


        }
    }

    void initial()
    {  int i;
        for(i=1; i<=N; i++)
            vizitat[i]=false;

    }


int main()
{

    f>>N>>M;
    int x, y, i, conexe=0;


    for(i=0; i<=M; i++)
    {   f>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    initial();

    for(i=1; i<=N; i++)
    {   if(vizitat[i]==false)
            {dfs(i); conexe++;}

    }

    ofstream g("dfs.out");
    g<<conexe;
    return 0;
}