All Tracks Algorithms Graphs Strongly Connected Components Problem

Joker is back
Tag(s):

Medium

Problem
Editorial
Analytics

Joker is back.

After Getting defeated at Gotham City , Joker went away into hiding and started assembling his own army to take his revenge from Batman . Meanwhile our hero Batman is enjoying in Vegas. As soon as Batman comes to know to know about the evil plans of Joker , he leaves for Gotham City at once.

The planning of Joker  is unique. He has recruited N armed thugs who are present in N different checkpoint in the city, exactly one thugs at each checkpoints. There are M one way roads in between these checkpoints. Now, it is necessary for every thug to visit any checkpoints if there exits a path. If , in this process the thug is unable to return to his allotted checkpoint, the checkpoint is left empty and Batman would destroy it. Find how many checkpoints destroyed by batman .

Input Format:

First line consists of a two space integers denoting N and M  and the following M lines consist of two space separated integers X and Y denoting there is a directed edge between vertices X and Y.

Output Format:

Find out numbers of checkpoint destroyed by batman.

Constraints:
1≤N≤100000

1≤M≤200000

1≤X,Y≤N

 

SAMPLE INPUT
4 4
1 2
2 3 
3 4
4 1
SAMPLE OUTPUT
0
Explanation

Thug at 1st checkpoints can go to 1->2->3->4->1 so he can come back to his checkpoint so batman cannot destroy his checkpoint , similarly for others.

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Уведомления
View All Notifications

?