-
Notifications
You must be signed in to change notification settings - Fork 0
/
1742.cpp
111 lines (89 loc) · 3.74 KB
/
1742.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_set>
#include <list>
using namespace std;
using Vertices = vector<unsigned long>;
// Минимальное количество групп будет равно количеству листьев в графе
// Если граф полностью замкнутый, то 1
unsigned long getMinGroups(const Vertices& fromVertices, const vector<unsigned long>& transitions) {
unordered_set<unsigned long> toVertices;
for (const auto from : fromVertices) {
toVertices.insert(transitions[from]);
}
const unsigned long diffSize = fromVertices.size() - toVertices.size();
return diffSize > 0 ? diffSize : 1;
}
// Максимальное количество групп будет равно количеству вершин, не входящих в цикл, + 1 на сам цикл (цикл есть всегда)
unsigned long getMaxGroups(const Vertices& fromVertices, const vector<unsigned long>& transitions) {
unordered_set<unsigned long> visited;
unsigned long top;
for(top = *fromVertices.begin();; top = transitions[top]) {
const auto res = visited.insert(top);
if (!res.second) {
break;
}
}
unsigned long cycleLen = 1;
for(unsigned long next = transitions[top]; next != top; next = transitions[next]) {
++cycleLen;
}
return 1 + fromVertices.size() - cycleLen;
}
// Графов может быть несколько, несвязанных между собой. Нужно просуммировать результаты для каждого
// Важно - использовать структуры с постоянным временем вставки и доступа к элементам, иначе просто не уложимся в отведенную секунду
int main()
{
unsigned long n;
cin >> n;
list<Vertices> verticesGroups;
vector<unsigned long> transitions(n);
vector<list<Vertices>::iterator> links(n, verticesGroups.end());
for (unsigned long from = 0; from < n; ++from) {
unsigned long p;
cin >> p;
unsigned long to = p - 1;
transitions[from] = to;
auto itFrom = links[from];
auto itTo = links[to];
if (itFrom == itTo) {
if (itFrom == verticesGroups.end()) {
verticesGroups.push_back({from});
links[from] = prev(verticesGroups.end());
links[to] = prev(verticesGroups.end());
} else {
itFrom->push_back(from);
}
continue;
}
if (itFrom == verticesGroups.end()) {
links[from] = itTo;
itTo->push_back(from);
continue;
}
if (itTo == verticesGroups.end()) {
links[to] = itFrom;
itFrom->push_back(from);
continue;
}
for (auto v : *itTo) {
links[v] = itFrom;
links[transitions[v]] = itFrom;
}
itFrom->reserve(itFrom->capacity() + itTo->size() + 1);
itFrom->insert(itFrom->end(), itTo->begin(), itTo->end());
itFrom->push_back(from);
verticesGroups.erase(itTo);
links[to] = itFrom;
}
const unsigned long minGroups = accumulate(verticesGroups.begin(), verticesGroups.end(), 0, [&transitions](unsigned long acc, const Vertices& g) {
return acc + getMinGroups(g, transitions);
});
const unsigned long maxGroups = accumulate(verticesGroups.begin(), verticesGroups.end(), 0, [&transitions](unsigned long acc, const Vertices& g) {
return acc + getMaxGroups(g, transitions);
});
cout << minGroups << " " << maxGroups << endl;
return 0;
}