All Tracks Algorithms Graphs Depth First Search Problem

Happy Vertices
Tag(s):

Easy

Problem
Editorial
Analytics

You are given a graph with $$N$$ vertices and $$M$$ edges. Master parent is the vertex which has no parent but may have 0 or more children. In any connected component of the graph,vertex with the lowest value in that component serves as the master parent.
A vertex is called happy if it has more children than its parent. Count the number of happy vertices in the given graph.The graph has no cycles or self loops.

Input Format:

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

Output Format:

Print the number of happy vertices in the graph.

Constraints:
$$ 1 \le N \le 100000$$
$$ 0 \le M \le N-1 $$
$$ 1 \le X, Y \le N $$

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

In this graph, we have vertices 1,2,3 and 4. Since 1 is the lowest among these, so it becomes the master vertex. Now, 1 has only 1 child while 2 has two children.So, 2 is a happy vertex. There are no more happy vertices in the graph.

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: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications