oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

teleportation Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

teleportation.html

Problem Description

Peanut lives in a city with N towns, numbered from 0 to N-1. There are T important trips that need to be made on a daily basis, with the ith trip being an important person requiring travel from town Ai to town Bi. Peanut wants to build teleporters such that all these trips can be accomplished instantaneously. Each teleporter can teleport people from a single town to another, unidirectionally. This means that if a teleporter were to be built to transport people from town a to town b, then another teleporter needs to be constructed to teleport people from town b to town a if backward instantaneous transport was required.

Help Peanut figure out the minimum number of teleporters that he needs to build.

Input

The first line of input will contain two integers, N and T. The next T lines of input will contain two integers each, containing Ai and Bi for each trip.

Output

The output should contain one line with one integer, the minimum number of teleporters Peanut has to build.

Limits

For all subtasks: (Ai, Bi) will be unique, Ai ≠ Bi.

Subtask 1 (32%): 1 ≤ N, T ≤ 1000.

Subtask 2 (31%): 1 ≤ N, T ≤ 200000, the graph formed by the edges (Ai, Bi) will contain no cycles.

Subtask 3 (37%): 1 ≤ N, T ≤ 200000.

Subtask 4 (0%): Sample Testcases.

Sample Input 1

4 5
0 1
0 2
0 3
1 2
1 3

Sample Output 1

3

Sample Input 2

4 6
0 1
0 3
1 2
1 3
2 1
2 3

Sample Output 2

4

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
132221s256MBMinimum
231201s256MBMinimum
337821s256MBMinimum
4021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o teleportation -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.