欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

VK Cup 2017 - Qualification 2 C. Online Courses In BSU(dfs)

程序员文章站 2022-07-12 12:35:17
...

题目链接
VK Cup 2017 - Qualification 2 C. Online Courses In BSU(dfs)
VK Cup 2017 - Qualification 2 C. Online Courses In BSU(dfs)
题意:总共有n个任务,有m个任务你必须完成,每个任务完成前可以有其他的子任务也必须完成,求完成的任务的顺序。
思路:一开始想着拓扑排序,但好像也不用那么反面,直接将那m个任务进行dfs,如果先后顺序反了则是-1.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+1;
int n,m,a[maxn],vis[maxn],pos[maxn];
vector<int>g[maxn],ans;
void dfs(int x)
{
	vis[x]=1;
	for(auto to:g[x])
	if(!vis[to]) dfs(to);
	ans.push_back(x);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d",&a[i]);
	for(int i=1,t,x;i<=n;++i)
	{
		scanf("%d",&t);
		while(t--)
		{
			scanf("%d",&x);
			g[i].push_back(x);
		}
	}
	for(int i=1;i<=m;++i) if(!vis[a[i]]) dfs(a[i]);
	for(int i=0;i<ans.size();++i) pos[ans[i]]=i;
	for(int i=0;i<ans.size();++i)
	{
		for(int j=0;j<g[ans[i]].size();++j)
		if(pos[g[ans[i]][j]]>i) {printf("-1\n");return 0;}
	}
	printf("%d\n",ans.size());
	for(int i:ans) printf("%d ",i);
}