Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- class PiggyBankSystem {
- private:
- int N;
- std::vector<int> keyPlacement;
- std::vector<bool> visited;
- std::vector<bool> inStack;
- public:
- PiggyBankSystem(int n, std::vector<int> keys)
- : N(n), keyPlacement(n + 1), visited(n + 1, false), inStack(n + 1, false) {
- for (int i = 1; i <= n; ++i) {
- keyPlacement[i] = keys[i];
- }
- }
- int findMinPiggyBanksToBreak() {
- int cycleCount = 0;
- for (int i = 1; i <= N; ++i) {
- if (!visited[i]) {
- int j = i;
- std::vector<int> path;
- bool isCycle = false;
- while (!visited[j]) {
- visited[j] = true;
- inStack[j] = true;
- path.push_back(j);
- j = keyPlacement[j];
- if (inStack[j]) {
- // Нашли цикл
- cycleCount++;
- break;
- }
- }
- // Пометим все узлы в пути как не входящие в стек
- for (int node : path) {
- inStack[node] = false;
- }
- }
- }
- return cycleCount;
- }
- };
- int main() {
- int N;
- std::cin >> N;
- std::vector<int> keys(N + 1);
- for (int i = 1; i <= N; ++i) {
- std::cin >> keys[i];
- }
- PiggyBankSystem system(N, keys);
- int result = system.findMinPiggyBanksToBreak();
- std::cout << result << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
