算法:哈希表
思路
不难看出,对于出现过的左项,记录其出现过即可。根据题目的数据范围,不难发现哈希表长度在$10^6$就可以了,不需要用unordered_map
(当然如果你想你也可以我不拦你)。申请计数器。对于所有出现在左项过的变量,记录为true
,如果有右项在表中为false
则为没有初始化,计数器增加$1$。最后输出答案即可。
注意:表中的第$0$项要预处理为
true
,因为常数项不需要初始化!
代码
#include <bits/stdc++.h>
using namespace std;
int k, n;
bool is_vis[1000010] = {1};
int x, y;
int ans;
int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
freopen(".input.txt", "r", stdin);
// freopen(".output.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 0; i < k; i++)
{
cin >> x >> y;
if (!is_vis[y])
ans++;
is_vis[x] = true;
}
cout << ans;
return 0;
}
复杂度分析
时间复杂度:$O(k + n)$
空间复杂度:$O(n)$