SHARE
TWEET

Algoritmul DFS - tutoriale-pe.net

ROMaurice Apr 26th, 2016 319 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Problema DFS - inforaena.ro - http://www.infoarena.ro/problema/dfs
  2. //Tutorialul complet, explicat - http://tutoriale-pe.net/parcugerea-adancime-dfs/
  3. #include    <fstream>
  4. #include    <vector>
  5.  
  6. using namespace std;
  7.  
  8. ifstream fin("dfs.in");
  9. ofstream fout("dfs.out");
  10.  
  11. const int NLIM = 100005;
  12.  
  13. int N, M;
  14. vector < int > Edge[NLIM];
  15.  
  16. bool beenThere[NLIM];
  17. int answer;
  18.  
  19. void DFS(int Node)
  20. {
  21.     beenThere[Node] = true;
  22.     for(unsigned int i = 0; i < Edge[Node].size(); i++)
  23.     {
  24.         int Next = Edge[Node][i];
  25.         if(!beenThere[Next])
  26.             DFS(Next);
  27.     }
  28. }
  29.  
  30. void Read()
  31. {
  32.     fin >> N >> M;
  33.     for(int i = 1; i <= M; i++)
  34.     {
  35.         int x, y;
  36.         fin >> x >> y;
  37.         Edge[x].push_back(y);
  38.         Edge[y].push_back(x);
  39.     }
  40.     for(int i = 1; i <= N; i++)
  41.     {
  42.         if(!beenThere[i])
  43.         {
  44.             answer += 1;
  45.             DFS(i);
  46.         }
  47.     }
  48.     fout << answer << "\n";
  49. }
  50.  
  51. int main()
  52. {
  53.     Read();
  54.     return 0;
  55. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top