SOLVE

LATER

Happy Vertices

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 $$

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

Initializing Code Editor...

{"da37745": "/pagelets/problem-author-tester/algorithm/happy-vertices/", "da3775b": "/pagelets/problems-hint/algorithm/happy-vertices/", "da3770c": "/pagelets/show-submission/algorithm/happy-vertices/", "da3772e": "/pagelets/suggested-problems/algorithm/happy-vertices/", "da37770": "/pagelets/recommended-problems/algorithm/happy-vertices/"}

{}

realtime.hackerearth.com

80

84ec45978c27f3dfae0f6d7630a691002fcb646c

58a29e5cae2309f04b28

/realtime/pusher/auth/