[pa] DFS - Cpp solution


  • 0
    D
    // Copyright 2018 Darius Neatu <neatudarius@gmail.com>
    
    // Ciclu in graf orientat
    // DFS - O(n + m)
    
    // 		Idee: gasim o muchie de intoarcere.
    
    // links:
    // - https://leetcode.com/problems/course-schedule/description/
    
    #include <bits/stdc++.h>
    using namespace std;
    
    #define NMAX 100009    // numar maxim de noduri
    
    // orice nod poate avea 3 stari cand vizitam graful:
    // NOT_DISCOVERED: inca nu l-am descoperit (initial toate sunt asa)
    // DISCOVERED    : atunci cand intram intr-un nod sa il vizitam recursiv
    // FINISHED      : marcam un nod ca fiind FINISHED imediat dupa ce am terminat
    //                 parcurgerea recursiva din acel nod
    #define NOT_DISCOVERED    0
    #define DISCOVERED        1
    #define FINISHED          2
    
    class Task {
    public:
      void solve(int n, vector< pair<int, int> > &edges) {
        read_input(n, edges);
        get_result();
        print_output();
      }
    
    private:
      // n = numar de noduri, m = numar de muchii
      int n, m;
    
      // adj[node] = lista de adiacenta a lui node
      vector<int> adj[NMAX];
    
      // graful este aciclic
      bool is_acyclic;
    
      void read_input(int n, vector< pair<int, int> > &edges) {
        // citesc numar de noduri, numar de muchii
        // cin >> n >> m;
        this->n = n;
        this->m = edges.size();
    
        for (int i = 1; i <= m; ++i) {
          int x, y;
          // cin >> x >> y; // citesc muchia x-y
          x = edges[i - 1].first + 1;
          y = edges[i - 1].second + 1;
            
          adj[x].push_back(y); // graful e orientat
        }
      }
    
      void get_result() {
        // visited[node] = starea lui nod in parcurgerea curenta
        vector<int> visited(n + 1, NOT_DISCOVERED);
        
        // presupun ca graful e aciclic
        is_acyclic = true;
          
        // incerc sa pornesc un DFS din fiecare nod nevizitat
        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                // vad daca pornind din i se gaseste un ciclu
                auto has_cycle = dfs(i, visited);
                
                // am gasit un ciclu (rosu)
                if (has_cycle) {
                    is_acyclic = false;
                    break;
                }
            }
        }
      }
        
      // dfs viziteaza recursiv pornind din node si returneaza
      // - true, daca a gasit un ciclu
      // - false, altfel
      bool dfs(int node, vector<int> &visited) {
        // marched nodul ca fiind descoperit
        // incep sa il vizitez
        visited[node] = DISCOVERED; 
        
        for (auto &x : adj[node]) {
            // am ciclu daca:
            // 1. daca x este un nod descoperit, dar neterminat
            // (muchie de intoarcere == DISCOVERED->DISCOVERED)
            // 2. x este un nod nou, dar vizitand recursiv prin x gasesc un ciclu
            if (visited[x] == DISCOVERED || dfs(x, visited)) {
                return true;
            }
        }
        
        // am terminat de vizitat nodul
        visited[node] = FINISHED;
        return false;
      }
    
      void print_output() {
        if (is_acyclic) {
          cout << "Graful ESTE aciclic!\n";
        } else {
          cout << "Graful ARE ciclu (rosu)!\n";
        }
      }
        
    public:
        bool get_acyclic() {
            return is_acyclic;
        }
    };
    
    
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
              int res;
            
              // aici este rezolvarea propriu-zisa
              Task *task = new Task();
              task->solve(numCourses, prerequisites);
              res = task->get_acyclic();
              delete task;
    
              return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.