前言

赛时苦战

1

个小时还是败给了 WA，看了同机房的大佬的 DFS 的解法后恍然大悟，故写此题解。

题目大意

有

N

种技能，给定

N

个数对

(A_1,B_1),\dots,(A_N,B_N)

。如果

(A_i,B_i)=(0,0)

，则已经学会了技能

i

。否则，在技能

A_i

或技能

B_i

有至少一个学会时，技能

i

也会学习，最后求能学会的技能的总数。

解题思路

DFS 即可。

考虑每个技能的前置技能，声明

vec[i]

存储所有以

i

为前置的技能，当

(A_i,B_i)=(0,0)

或技能

i

已经学会时，那么直接 DFS 所有以

i

为前置的技能即可，同时还可以开一个标记数组因为当一个技能被搜索过时，所有以它为前置的技能都已被学会了，特别的，技能可以不按照输入顺序学习，最后复杂度是

O(N)

的，因为标记数组的原因没有重复搜索。

AC 代码

CPP

#include<bits/stdc++.h>
#define re ree()
#define pbk push_back
using namespace std;
long long ree(){long long f=1,k=0;char c=getchar();while(c<'0'||c>'9'){if(c == '-')f = -1;c=getchar();}while(c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}return f*k;}
long long n,m,k,bo[500010],cnt[500010],ans,vis[500010];
struct node{
	long long a,b,i;
}a[500100];
vector<int> vec[500010];
void dfs(int x)				 //dfs 
{
	if(vis[x]!=0)
	{
		return;
	}
	ans++;
	vis[x]=1;
	for(int i=0;i<vec[x].size();i++)
	{
		dfs(vec[x][i]);
	}
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		a[i].a=re;
		a[i].b=re;
		vec[a[i].a].pbk(i);
		vec[a[i].b].pbk(i);
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i].a==0&&a[i].b==0)
		{
			dfs(i);
		}
	}
	cout<<ans;
	return 0;
}

题解：AT_abc424_c [ABC424C] New Skill Acquired

文章操作

前言

题目大意

解题思路

AC 代码

相关推荐

评论

题解：AT_abc424_c [ABC424C] New Skill Acquired