-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathP1983.cpp
More file actions
101 lines (95 loc) · 2.43 KB
/
P1983.cpp
File metadata and controls
101 lines (95 loc) · 2.43 KB
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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef unsigned short word;
#define WORD_MIN 0x0000
#define WORD_MAX 0xffff
class TopSort {
public:
word getMaxDist(vector<word> * graph, size_t nv, word * in_degree);
private:
word * level_;
queue<word> vqueue_;
};
word TopSort::getMaxDist(vector<word>* graph, size_t nv, word * in_degree) {
level_ = new word[nv];
memset(level_, 0, nv * sizeof(word));
for (size_t i = 0; i < nv; i++)
if (!in_degree[i]) {
vqueue_.push(i);
}
word max_dist = 0;
word front_v, adj_v;
while (!vqueue_.empty()) {
front_v = vqueue_.front();
vqueue_.pop();
if (level_[front_v] > max_dist) max_dist = level_[front_v];
for (auto it = graph[front_v].begin(); it != graph[front_v].end(); it++) {
adj_v = *it;
if (level_[front_v] + 1 > level_[adj_v]) {
level_[adj_v] = level_[front_v] + 1;
}
if ((--in_degree[adj_v]) == 0) {
vqueue_.push(adj_v);
}
}
}
free(level_);
return max_dist;
}
int main() {
word n, m;
scanf("%hd %hd", &n, &m);
vector<word> * graph = new vector<word>[n];
word * in_degree = new word[n];
memset(in_degree, 0, n * sizeof(word));
bool * stop = new bool[n];
vector<word> stop_stations;
bool ** has_edge = new bool*[n];
for (size_t i = 0; i < n; i++) {
has_edge[i] = new bool[n];
memset(has_edge[i], false, n * sizeof(bool));
}
word s, station, max_station, min_station;
for (size_t i = 0, j; i < m; i++) {
memset(stop, false, n * sizeof(bool));
stop_stations.clear();
scanf("%hd", &s);
max_station = WORD_MIN;
min_station = WORD_MAX;
for (j = 0; j < s; j++) {
scanf("%hd", &station);
station--;
stop[station] = true;
stop_stations.push_back(station);
if (station > max_station) max_station = station;
if (station < min_station) min_station = station;
}
for (j = min_station + 1; j < max_station; j++) {
if (!stop[j]) {
for (word stop_station : stop_stations) {
if (has_edge[j][stop_station]) continue;
graph[j].push_back(stop_station);
in_degree[stop_station]++;
has_edge[j][stop_station] = true;
}
}
}
}
free(stop);
vector<word>().swap(stop_stations);
for (size_t i = 0; i < n; i++) {
free(has_edge[i]);
}
free(has_edge);
TopSort topsort;
word max_dist = topsort.getMaxDist(graph, n, in_degree);
printf("%hd", max_dist + 1);
for (size_t i = 0; i < n; i++)
vector<word>().swap(graph[i]);
free(in_degree);
return 0;
}