Advertisement
Guest User

Death Star Towers

a guest
Aug 24th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class DeathStarDestroyer {
  6. private:
  7.     int numTowers;
  8.     vector<vector<int>> energyLinks;
  9.     vector<int> grad;
  10. public:
  11.     DeathStarDestroyer(int numTowers) {
  12.       this->numTowers = numTowers;
  13.       energyLinks.resize(numTowers);
  14.       for (int i = 0; i < numTowers; i++) {
  15.           grad.push_back(0);
  16.       }
  17.     }
  18.  
  19.     void addEnergyLink(int source, int destination) {
  20.         energyLinks[source].push_back(destination);
  21.         grad[destination]++;
  22.     }
  23.  
  24.        
  25.     // TODO: Calculeaza nr minim de turnuri de comanda ce trebuie distruse
  26.     void dfs(int nod, vector<bool> &viz) {
  27.         viz[nod] = 1;
  28.         for (int i = 0; i < energyLinks[nod].size(); i++) {
  29.             if (viz[energyLinks[nod][i]] == 0) {
  30.                 dfs(energyLinks[nod][i], viz);
  31.             }
  32.         }
  33.     }
  34.     int getMinDestroyedTowers() {
  35.         int minDestroyedTowers = 0;
  36.         vector<bool> viz;
  37.         for (int i = 0; i < numTowers; i++) {
  38.             viz.push_back(0);
  39.         }
  40.         for (int i = 0; i < numTowers; i++) {
  41.             if (viz[i] == 0 && grad[i] == 0) {
  42.                 minDestroyedTowers++;
  43.                 dfs(i, viz);
  44.             }
  45.         }
  46.         return minDestroyedTowers;
  47.     }
  48.    
  49. };
  50.  
  51. // NU MODIFICA FUNCTIA MAIN!
  52. int main() {
  53.     int numTowers, numEnergyLinks;
  54.     int source, destination;
  55.     cin >> numTowers >> numEnergyLinks;
  56.  
  57.     DeathStarDestroyer destroyer(numTowers);
  58.     for (int iLink = 0; iLink < numEnergyLinks; ++iLink) {
  59.       cin >> source >> destination;
  60.       destroyer.addEnergyLink(source, destination);
  61.     }
  62.  
  63.     cout << destroyer.getMinDestroyedTowers() << "\n";
  64.  
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement