Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- class DeathStarDestroyer {
- private:
- int numTowers;
- vector<vector<int>> energyLinks;
- vector<int> grad;
- public:
- DeathStarDestroyer(int numTowers) {
- this->numTowers = numTowers;
- energyLinks.resize(numTowers);
- for (int i = 0; i < numTowers; i++) {
- grad.push_back(0);
- }
- }
- void addEnergyLink(int source, int destination) {
- energyLinks[source].push_back(destination);
- grad[destination]++;
- }
- // TODO: Calculeaza nr minim de turnuri de comanda ce trebuie distruse
- void dfs(int nod, vector<bool> &viz) {
- viz[nod] = 1;
- for (int i = 0; i < energyLinks[nod].size(); i++) {
- if (viz[energyLinks[nod][i]] == 0) {
- dfs(energyLinks[nod][i], viz);
- }
- }
- }
- int getMinDestroyedTowers() {
- int minDestroyedTowers = 0;
- vector<bool> viz;
- for (int i = 0; i < numTowers; i++) {
- viz.push_back(0);
- }
- for (int i = 0; i < numTowers; i++) {
- if (viz[i] == 0 && grad[i] == 0) {
- minDestroyedTowers++;
- dfs(i, viz);
- }
- }
- return minDestroyedTowers;
- }
- };
- // NU MODIFICA FUNCTIA MAIN!
- int main() {
- int numTowers, numEnergyLinks;
- int source, destination;
- cin >> numTowers >> numEnergyLinks;
- DeathStarDestroyer destroyer(numTowers);
- for (int iLink = 0; iLink < numEnergyLinks; ++iLink) {
- cin >> source >> destination;
- destroyer.addEnergyLink(source, destination);
- }
- cout << destroyer.getMinDestroyedTowers() << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement