CSES - HIIT Open 2017 - Results
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.03 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.05 sdetails
#50.13 sdetails
#60.09 sdetails
#70.12 sdetails
#80.09 sdetails
#90.12 sdetails
#100.08 sdetails
#110.10 sdetails
#120.10 sdetails
#130.13 sdetails
#140.12 sdetails
#150.08 sdetails
#16ACCEPTED0.06 sdetails
#17ACCEPTED0.06 sdetails

### Compiler report

```input/code.cpp: In function 'int main()':
input/code.cpp:49:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ts.size(); ++i) {
^```

### Code

```#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
typedef vector<int> vi;
#define PB push_back

int n, m;
vi g[505];

vi ts;
int v1[505];
int comp[505];

vector<int> cws;

int v7[505];

void dfs1(int s) {
if (v1[s]) return;
v1[s] = 1;
for (int a : g[s]) {
dfs1(a);
}
ts.push_back(s);
}

void dfs2(int s, int cc) {
if (comp[s]) return;
comp[s] = cc;
for (int a : g[s]) {
dfs2(a, cc);
}
}

int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
}
for (int i = 1; i <= n; ++i) dfs1(i);
reverse(ts.begin(), ts.end());

int ccomp = 0;
for (int i = 0; i < ts.size(); ++i) {
int cur = ts[i];
if (comp[cur] == 0) {
ccomp++;
dfs2(cur, ccomp);
cws.PB(cur);
}
}

int res = 0;
while (cws.size() != 0) {
int c1 = cws[cws.size()-1];
cws.pop_back();
v7[c1] = 1;

int c2 = -1;
if (cws.size() != 0)  {
c2 = cws[cws.size()-1];
cws.pop_back();
v7[c2] = 1;
}

res++;
for (int a : g[c1]) {
if (v7[a] == 0) {
v7[a] = 1;
cws.PB(a);
}
}
if (c2 != -1) {
for (int b : g[c2]) {
if (v7[b] == 0) {
v7[b] = 1;
cws.PB(b);
}
}
}
}
cout << res << "\n";
return 0;
}
```

### Test details

#### Test 1

Verdict: ACCEPTED

input
1 0

correct output
1

user output
1

#### Test 2

Verdict: ACCEPTED

input
2 0

correct output
1

user output
1

#### Test 3

Verdict: ACCEPTED

input
2 1
2 1

correct output
2

user output
2

#### Test 4

Verdict: ACCEPTED

input
500 0

correct output
250

user output
250

Verdict:

input
500 124750
66 104
50 159
173 457
200 154
...

correct output
500

user output
251

Verdict:

input
500 96771
376 390
243 497
417 360
107 80
...

correct output
413

user output
251

Verdict:

input
500 106799
96 245
68 62
122 119
460 454
...

correct output
433

user output
251

Verdict:

input
500 83550
76 338
111 174
88 142
114 463
...

correct output
365

user output
250

Verdict:

input
500 98051
281 60
312 284
270 474
385 224
...

correct output
410

user output
251

Verdict:

input
500 86622
5 320
50 107
182 483
385 500
...

correct output
372

user output
251

Verdict:

input
500 99445
421 286
392 406
155 290
475 453
...

correct output
396

user output
251

Verdict:

input
500 99832
283 149
315 396
264 422
224 388
...

correct output
410

user output
250

Verdict:

input
500 116149
446 185
232 35
498 391
189 63
...

correct output
457

user output
251

Verdict:

input
500 84757
71 205
286 360
184 486
30 228
...

correct output
364

user output
251

Verdict:

input
500 108617
126 250
76 224
449 69
200 63
...

correct output
439

user output
251

#### Test 16

Verdict: ACCEPTED

input
10 20
7 8
1 3
4 8
5 9
...

correct output
5

user output
5

#### Test 17

Verdict: ACCEPTED

input
10 20
2 9
9 8
4 3
7 3
...

correct output
5

user output
5