PROBLEM LINK:
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)