KQM19A - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester 1: Harsh Raj
Tester 2: Mostafijur Riju
Editorialist: Chandan Boruah

DIFFICULTY:

EASY

PREREQUISITES:

Tree

PROBLEM:

Given an adjacency list of a tree, find the number of leaf nodes in the tree.

QUICK EXPLANATION:

Since the leaf nodes have no outgoing edges, the leaf nodes will be the nodes not present in the adjacency list.

EXPLANATION:

The leaf nodes do not have outgoing edges, so they will not be listed in the adjacency list. So the number of leaf nodes would be the difference between the total number of nodes and the number of nodes with outgoing edges. Actually calculating the nodes would TLE cause the constraints were designed that way.

SOLUTIONS:

Setter's Solution 
using System;
using System.Collections.Generic;
class some
{
	public static void Main()
	{
		int n=int.Parse(Console.ReadLine());
		int t=int.Parse(Console.ReadLine());
		Console.WriteLine(n-t);
	}
}
harshraj22's Solution 
from collections import defaultdict

n = int(input())
graph = [[] for _ in range(n)]
t = int(input())

for _ in range(t):
	par = int(input())
	graph[par].extend(list(map(int,input().strip().split())))

ans = 0
for lst in graph:
	if len(lst) == 0:
	    ans += 1

print(ans)