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
|
// 1466. Reorder Routes to Make All Paths Lead to the City Zero
#include <stdio.h>
#include <stdlib.h>
struct node {
int *in;
int in_cnt;
int in_size;
int *out;
int out_cnt;
int out_size;
};
void dfs(struct node *n, int curr, int *ans) {
for (int i = 0; i < n[curr].in_cnt; i++) {
if (n[curr].in[i] != -1) {
int next = n[curr].in[i];
for (int j = 0; j < n[next].out_cnt; j++) {
if (n[next].out[j] == curr) {
n[next].out[j] = -1;
n[curr].in[i] = -1;
dfs(n, next, ans);
}
}
}
}
for (int i = 0; i < n[curr].out_cnt; i++) {
if (n[curr].out[i] != -1) {
int next = n[curr].out[i];
for (int j = 0; j < n[next].in_cnt; j++) {
if (n[next].in[j] == curr) {
n[next].in[j] = -1;
n[curr].out[i] = -1;
++*ans;
dfs(n, next, ans);
}
}
}
}
}
int minReorder(int n, int **connections, int connections_size,
int *connections_col_size) {
struct node *ns = malloc(n * sizeof(struct node));
for (int i = 0; i < n; i++) {
ns[i].in = malloc(sizeof(int));
ns[i].in_cnt = 0;
ns[i].in_size = 1;
ns[i].out = malloc(sizeof(int));
ns[i].out_cnt = 0;
ns[i].out_size = 1;
}
for (int i = 0; i < connections_size; i++) {
int out_idx = connections[i][0];
ns[out_idx].out[ns[out_idx].out_cnt] = connections[i][0];
++ns[out_idx].out_cnt;
if (ns[out_idx].out_cnt == ns[out_idx].out_size) {
ns[out_idx].out_size *= 2;
ns[out_idx].out =
realloc(ns[out_idx].out, ns[out_idx].out_size * sizeof(int));
}
int in_idx = connections[i][1];
ns[in_idx].in[ns[in_idx].in_cnt] = connections[i][0];
++ns[in_idx].in_cnt;
if (ns[in_idx].in_cnt == ns[in_idx].in_size) {
ns[in_idx].in_size *= 2;
ns[in_idx].in = realloc(ns[in_idx].in, ns[in_idx].in_size * sizeof(int));
}
}
int ans = 0;
dfs(ns, 0, &ans);
for (int i = 0; i < n; i++) {
free(ns[i].in);
free(ns[i].out);
}
free(ns);
return ans;
}
int main() {
int c1[5][2] = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
int c2[4][2] = {{1, 0}, {1, 2}, {3, 2}, {3, 4}};
int c1_c_s[] = {5}, c2_c_s[] = {4};
printf("%d\n", minReorder(6, c1, 5, c1_c_s));
printf("%d\n", minReorder(5, c2, 4, c2_c_s));
}
|