スキルを頂点とし、未習得な各スキル \(i\) について、スキル \(A_i\) からスキル \(i\)、スキル \(B_i\) からスキル \(i\) へ有向辺を張ったグラフを考えます。このグラフにおいて、既に習得済みのスキルから到達可能であることが習得可能であることと同値になります。

よって、このグラフ上で習得済みの各スキルを始点に DFS または BFS により各頂点に到達可能できるかどうかを判定すればよく、\(O(N)\) でこの問題を解くことができます。

なお、仮想的な「スキル \(0\)」が存在するとし、スキル \(0\) のみが習得済みであると考えることで、単一始点とすることもできます。

writer解(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解(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;
}