-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathP2863.c
More file actions
99 lines (86 loc) · 2.07 KB
/
P2863.c
File metadata and controls
99 lines (86 loc) · 2.07 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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 10004
typedef struct vector {
int size;
int cap;
int *arr;
} vector;
static inline vector *vcreate() {
vector *v = (vector *)malloc(sizeof(*v));
v->size = 0;
v->cap = 10;
v->arr = (int *)malloc(v->cap*sizeof(int));
return v;
}
static inline void vfree(vector *v) {
if (v == NULL) return;
if (v->arr) free(v->arr);
free(v);
}
static inline void vadd(vector *v, int ele) {
if (v == NULL) return;
if (++v->size > v->cap) {
v->cap *= 2;
v->arr = realloc(v->arr, v->cap*sizeof(int));
}
v->arr[v->size - 1] = ele;
}
static inline int vsize(vector *v) { return v->size; }
static inline int vget(vector *v, int i) { return v->arr[i]; }
static inline void vpush(vector *v, int ele) { vadd(v, ele); }
static inline int vpop(vector *v) { return v->arr[--v->size]; }
vector *graph[N];
int dfn[N], low[N];
bool instack[N];
int count, ans;
vector *stack;
static inline int min(int a, int b) { return a < b ? a : b; }
void dfs(int v) {
if (dfn[v]) return;
dfn[v] = low[v] = count++;
vpush(stack, v);
instack[v] = true;
int w;
for (int i = 0; i < vsize(graph[v]); i++) {
w = vget(graph[v], i);
if (!dfn[w]) {
dfs(w);
low[v] = min(low[v], low[w]);
} else if (instack[w]) {
low[v] = min(low[v], dfn[w]);
}
}
int csize = 0;
if (dfn[v] == low[v]) {
while ((w = vpop(stack)) != v) {
csize++;
instack[w] = false;
}
csize++;
instack[v] = false;
if (csize > 1) ans++;
}
}
int main() {
int n, m, i, v, w;
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) graph[i] = vcreate();
for (i = 0; i < m; i++) {
scanf("%d %d", &v, &w);
v--, w--;
vadd(graph[v], w);
}
stack = vcreate();
ans = 0;
for (i = 0; i < n; i++) {
count = 0;
dfs(i);
}
printf("%d\n", ans);
for (i = 0; i < n; i++)
vfree(graph[i]);
vfree(stack);
exit(0);
}