题解：AT_abc424_c [ABC424C] New Skill Acquired

题意

就是有一些技能，得到技能

i

之前必须解锁其他两个技能

a_i

，

b_i

中的一个，问最后最多有几个技能。

思路

一开始就有的肯定是

a_i=b_i=0

的技能。

对于一个新解锁的技能

i

，他能对技能

j

直接产生影响当且仅当

a_j

或

b_j

为

i

。

然后就可以把已解锁技能放进一个队列，然后把凡是他能解锁的都解锁了，并放入队列，当然每个技能放一次（计算一次影响）就够了。

然后就没了。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+15; 
int vis[N];
vector<int>g[N];
signed main()
{
	int n;
	cin>>n;
	queue<int>q;
	for(int i=1;i<=n;i++) 
	{
		int a,b;
		cin>>a>>b;
		if(a==b&&a==0)
		{
			q.push(i);
			continue;
		}
		g[a].push_back(i);//a做完就可以做i了
		if(a!=b)g[b].push_back(i);
	}
	int res=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(vis[u]) continue;
		res++;
		vis[u]=1;
		for(auto v:g[u])
		{
			if(vis[v]) continue;
			q.push(v);
		}
	}
	cout<<res<<endl;
	return 0;
}

题解：AT_abc424_c [ABC424C] New Skill Acquired

文章操作

题意

思路

代码

相关推荐

评论

题解：AT_abc424_c [ABC424C] New Skill Acquired