[pa] Hahn - C++ solution


  • 0
    D
    // Copyright 2018 Darius Neatu <neatudarius@gmail.com>
    
    // Ciclu in graf orientat
    // Kahn - O(n + m)
    
    // 		Idee: se incearca sa se gaseasca o sortare topologica cu algoritmul
    // lui Kahn. Daca la finalul alforitmului exista cel putin un nod cu grad
    // intern mai mare ca zero, atunci graful are ciclu (nu s-a putut sorta
    // topologic).
    
    // links:
    // - https://leetcode.com/problems/course-schedule/description/
    
    #include <bits/stdc++.h>
    using namespace std;
    
    #define NMAX 100009    // numar maxim de noduri
    
    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];
      // (observatie: prin conventie nodurile sunt indexate de la 1
      //  deci listele sunt adj[1], ..., adj[n])
    
      // in_degree[i] = gradul intern al nodului i
      vector<int> in_degree;
      // grad intern == nr de muchii care intra in i
      // arce de forma x -> i
    
      // 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();
    
        // grad intern 0 pentru toate nodurile... momentan
        in_degree = vector<int>(n + 1, 0);
    
        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
          ++in_degree[y];      // inca o muchie care intra in y
        }
      }
    
      void get_result() {
        // se va dace o parcurge BFS din TOATE nodurile cu grad intern 0
        bfs();
    
        // verifica ca s-a realizat o sortare topologica valida!
        // ce inseamna asta? s-au sters toate muchiile din graf.
        // daca nu s-a sters tot, atunci graful este ciclic!
        bool is_valid = true;
        for (int i = 1; i <= n; ++i) {
          if (in_degree[i] > 0) {
            is_valid = false;
            break;
          }
        }
    
        if (is_valid) {
        	is_acyclic = true;  // graf ACICLIC (valid topsort)
      	} else {
      		is_acyclic = false; // graf CICLIC  (invalid topsort)
        }
      }
    
      void bfs() {
        // declaram o coada in care putem baga noduri
        queue<int> Q;
    
        // pasul initial: pun in coada TOATE nodurile cu grad intern 0
        for (int i = 1; i <= n; ++i) {
          if (in_degree[i] == 0) {
            Q.push(i);
          }
        }
    
        // parcurg in latime graful
        while (!Q.empty()) {
          // SCOT primul nod din coada
          int node = Q.front();
          Q.pop();
    
          // Ii parcurg toti vecinii
          for (auto &it : adj[node]) {
            // sterg muchia node->it
            // obs1. NU e nevoie sa o sterg la propriu
            //       Daca nu am cicluri, nu se va ajunge aici.
            // obs2. Simulez stergerea prin scaderea gradului intern a lui it
            --in_degree[it];
    
            // daca it a ajuns nod cu grad intern 0, atunci este adaugat in coada
            if (in_degree[it] == 0) {
              Q.push(it);
            }
          }
        }
      }
    
      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.