1007. Is It a Forest, and How Many Trees
A plantation has n nodes and m branches, each joining two nodes. A branch may
join a node to itself, and the same pair may be branched more than once.
A FOREST is a collection of trees: a graph with no closed loop anywhere. Print the number of
trees if the plantation is a forest, and the exact words NOT A FOREST otherwise.
6 nodes, branches (1 2)(2 3)(4 5)(5 6) -> 2
3 nodes, branches (1 2)(2 3)(1 3) -> NOT A FOREST
4 nodes, no branches -> 4
2 nodes, branches (1 2)(2 1) -> NOT A FOREST
3 nodes, branch (2 2) -> NOT A FOREST
The last two are the ones that catch people. Two branches between the same pair form a loop of length two, and a branch from a node to itself is a loop of length one. Both are closed loops and both disqualify the plantation.
## What most people try first
Compare m against n - 1. That is the test for a single tree, not for a forest: a forest
of c trees has n - c branches, and c is not known in advance. It is also useless on
its own, because an edge count says nothing about where the edges are: the second example has
3 nodes and 3 branches, and so does a plantation with a triangle plus a lone node, which is
also not a forest but for a different reason.
The other common start is a traversal that watches for an already-visited node, which works but has to remember which branch it arrived on so that the branch back does not look like a loop, and that guard is wrong when the same pair is branched twice.
## One sweep that answers both parts
trees = n
for each branch (u, v):
if find(u) == find(v):
print NOT A FOREST and stop
merge them
trees = trees - 1
print trees
## Why stopping at the first failure is safe
A branch whose two ends already share a root closes a loop: there is already a path between them made of earlier branches, and this branch is one more. So the plantation is not a forest and nothing later can change that. Conversely, if no branch ever fails the test, then every branch joined two separate pieces, so no branch ever created a second route between two nodes and there is no loop anywhere.
The two nasty cases fall out of that test without any special handling. A repeated pair fails
because the first copy already merged them. A self branch fails because find(u) equals
find(u).
## Why the tree count is n minus the merges
Every node starts as a tree of one. Each successful merge joins two trees into one, lowering
the count by one, and since the answer is only printed when every branch merged, the count is
n - m. Writing n - m directly is correct here and only here, which is why the counter is
written out instead: it is the version that survives being adapted.
## Cross-reference
Problem 370 asks whether the graph is ONE tree, which is connected AND without a loop, and its
input forbids self loops and repeated edges so its m == n - 1 shortcut is available. Here
disconnected is perfectly fine, the forbidden inputs are allowed, and the count of trees is
part of the answer. Problem 1006 prints the same merge test per branch instead of stopping at
the first failure.
## Cost
Time O((n + m) alpha(n)). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, and a pair may repeat.
Input
The first line contains two integers n and m.
Each of the next m lines contains two integers u and v, the two ends of one branch.
Output
Print one line: the number of trees if the plantation is a forest, or the words NOT A FOREST spelled exactly like that in capitals with single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.