TikTok OA 面试真题解析：Viral Campaign 最少初始传播人数

Given an integer n representing the total number of TikTok users, along with two lists, influencers and followers, each of size n.

For each index i, influencers[i] represents an influencer and followers[i] represents the user who follows that influencer. If followers[i] is -1, it indicates that the corresponding influencer has no followers.

It is important to note the following:

• Some users may not have any followers; in such cases, followers[i] will be set to -1.
• There may be mutual follow relationships, i.e., user a may follow user b, and user b may follow user a.
• Some users might appear in the influencers list but not in the followers list. In such cases, assume these influencers follow nobody.
• Some users might appear in neither list. In such cases, assume these users neither follow nor influence anyone, but they are still considered individual TikTok users.

Your goal is to compute the size of the smallest set of users to whom the trend should initially be introduced, ensuring that the trend ultimately reaches every user on the platform.

Example

n = 4
influencers = [1, 2, 3, 4]
followers = [1, 3, 2, -1]

Consider introducing the viral trend to users 4 and 1. Note that nobody follows influencer 4, so we must introduce the trend directly to influencer 4. Once the trend is introduced to influencer 1, it is propagated to influencer 3, who follows influencer 1. Influencer 3 in turn propagates the trend to influencer 2, who follows influencer 3. As a result, the viral trend eventually reaches all the users. Thus, the minimum number of users required to initiate the trend is 2.

Function Description

Complete the function findMinimumInfluencers in the editor below.

Function Parameters

• int influencers[n]: an array where influencers[i] denotes the influencers
• int followers[n]: an array where followers[i] denotes the followers such that followers[i] follows influencers[i]

Returns

• int: the minimum number of influencers to whom the product should be introduced

这道题本质上是在一个有向图里找“最少起点数”，使得从这些点出发可以覆盖所有用户。把每个用户看成图的一个点，<code>influencers[i]</code> 指向 <code>followers[i]</code>，然后对图做强连通分量缩点；缩点后形成 DAG，答案就是入度为 0 的 SCC 数量，因为这些分量没有外部路径可达，必须被直接点亮。由于题目允许单向、互相关注以及部分用户缺失，构图时只需保留真实出现的边，并把所有用户都纳入考虑；整体可用 Tarjan 或 Kosaraju 在 <code>O(n)</code> 到 <code>O(n+m)</code> 的复杂度内完成。