Consider a directed graph whose vertices being the skills and, for each unacquired skill \(i\), with a directed edge from skill \(A_i\) to skill \(i\) and another from skill \(B_i\) to skill \(i\). In this graph, a skill is eventually acquirable if and only if it is reachable from an initially learned skill.

Therefore, it is sufficient to check reachability of each vertex on this graph, by performing a DFS (Depth-First Search) or a BFS (Breadth-First Search) starting from the initially learned skills. This way, the problem can be solved in \(O(N)\) time.

One can define a “virtual skill \(0\)” and only skill \(0\) is initially learned. This way, the DFS or BFS can be started from a single vertex.

Writer’s solution (Python)

import sys
sys.setrecursionlimit(10**9)

N=int(input())
G=[[] for _ in range(N+1)]

for i in range(1,N+1):
  a,b=map(int,input().split())
  G[a].append(i)
  G[b].append(i)

ok=[0]*(N+1)
ok[0]=1

def dfs(v):
  ok[v]=1
  for vv in G[v]:
    if not ok[vv]:
      dfs(vv)

dfs(0)

print(sum(ok)-1)

Writer’s solution (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N;
	cin >> N;
	vector<vector<int>>G(N+1);
	
	for(int i=1;i<=N;i++){
		int a,b;
		cin >> a >> b;
		G[a].push_back(i);
		G[b].push_back(i);
	}

	vector<bool>ok(N+1);
	ok[0]=true;

	auto dfs=[&](auto self,int v)->void{
		ok[v]=true;
		for(auto vv:G[v])if(!ok[vv]){
			self(self,vv);
		}
	};
	
	dfs(dfs,0);
	
	int ans=0;
	for(auto x:ok)ans+=x;
	cout << ans-1 << endl;
}