Cod sursa(job #2207613)

Utilizator crixus97Cristi crixus97 Data 26 mai 2018 09:05:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <list>
#include <vector>
#include <fstream>
using namespace std;
vector <list<int>> M;
vector <int> viz;
list<int> u;
ifstream f("dfs.in");
ofstream g("dfs.out");
void dfs(int nod)
{

    if(viz[nod]==0)
    {
        viz[nod]=1;
        for(list<int> :: iterator y=M[nod].begin(); y!=M[nod].end(); y++)
            if(viz[*y]==0)
                dfs(*y);
    }
}
int main()
{
    unsigned long long n,m,i,a,b,ok,nr=0;
    f>>n>>m;
    M.resize(n+1);
    viz.resize(n+1);
    for(i=0; i<m; i++)
    {
        f>>a>>b;
        M[a].push_back(b);
        M[b].push_back(a);
    }

   /* for(i=0; i<M.size(); i++)
    {
        cout<<i<<" ";
        for(list<int> :: iterator y=M[i].begin(); y!=M[i].end(); y++)
            cout<<" "<< *y;
        cout<<endl;
    }*/
    for(i=1; i<=n; i++)
        viz[i]=0;
    int nod=1;
    int nr_ori=0;
    for(i=1; i<=n; i++)
        if(viz[i]==0)
        {
            nr_ori++;
            dfs(i);
        }
   // for(i=1; i<=n; i++)
       // cout<<viz[i]<<" ";
    g<<nr_ori;
}