Cod sursa(job #1766729)

Utilizator marcdariaDaria Marc marcdaria Data 28 septembrie 2016 15:15:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
 #include <fstream>
 #include <vector>

using namespace std;

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

 const int n_max=100005;
 int n,m,viz[n_max];
 vector <int> v[n_max];

 void citire()
 {
     fin>>n>>m;
     for(int i=1;i<=m;++i)
     {
         int x,y;
         fin>>x>>y;
         v[x].push_back(y);
         v[y].push_back(x);
     }
 }

 void dfs(int nod)
 {
     viz[nod]=1;
     for(int i=0;i<v[nod].size();++i)
     if(viz[v[nod][i]]==0)
     {
         viz[v[nod][i]]=1;
         dfs(v[nod][i]);
     }
 }

 int main()
 {
     citire();
     int cnt=0;
     for(int i=1;i<=n;++i)
     if(viz[i]==0)
     {
      cnt++;
      dfs(i);
     }
     fout<<cnt;

     return 0;
 }