Cod sursa(job #1427904)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 3 mai 2015 12:02:43
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

 vector<int> graph[100000];
 bool vist[100000];
 int nr=0,n,m,a,b;

void dfs(int vert)
{
    vist[vert]=true;

      for (int i=0;i<graph[vert].size();i++)
      {
          if (!vist[graph[vert][i]])
                     dfs(graph[vert][i]);
      }
}

int main()
{
    fin >> n >> m;

     for (int i=0;i<m;i++)
     {
         fin >> a >> b;
         graph[a].push_back(b);
         graph[b].push_back(a);
     }

    for (int i=1;i<=n;i++)
      if (!vist[i])
        {
          nr++;
          dfs(i);
        }
    fout << nr << "\n";
    return 0;
}