CF770C Online Courses In BSU

知识点：深搜，拓扑排序

难度：4

感觉自己对知识点的掌握还是不够熟练，这个题用我现在掌握的知识点来解决的话就是深搜+拓扑排序，还是看了题解才想到的，首先是判断有没有解，如果主课存在于环上，或者主课前面的先修课有环，那么就是无解的，所以我们先用拓扑排序来判断有解，具体的思路就是拓扑排序完之后看看排好的序列里面是不是所有的主课都出现了，是就是有解，继续，不是那么就是无解

接下来是有解求解，这里使用的是深搜，就是我们额外建一个反图，然后以那些没被访问过的主课作为开头，去深搜，同时统计答案，这样最后就能得到答案，并且输出的时候把拓扑序列里面的刚被访问过的点输出就行了，这个题稍微有点复杂，但是以我的知识储备应该是能做出来的，没有什么超纲的知识，但是还是看了看题解才想起来是怎么做的

#include 
 
using namespace std;
 
const int N = 1e5 + 5;
 
int n, k, tot, ver[N], nxt[N], head[N];
int tot2, ver2[N], nxt2[N], head2[N];
int indeg[N], a[N], vis[N], ans, Hash[N];
vector<int> v;
 
void add(int x, int y) {
	ver[++tot] = y;
	nxt[tot] = head[x]; head[x] = tot;
}
 
void add2(int x, int y) {
	ver2[++tot2] = y;
	nxt2[tot2] = head2[x]; head2[x] = tot2;
}
 
void topo() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (!indeg[i]) q.push(i);
	}
	while (!q.empty()) {
		int now = q.front(); q.pop();
		v.push_back(now);
		for (int i = head[now]; i; i = nxt[i]) {
			int y = ver[i];
			if (--indeg[y] == 0) q.push(y);
		}
	}
}
 
void dfs(int x) {
	vis[x] = 1;
	ans++;
	for (int i = head2[x]; i; i = nxt2[i]) {
		int y = ver2[i];
		if (!vis[y]) dfs(y);
	}
}
 
int main() {
	cin >> n >> k;
	for (int i = 1; i <= k; i++) {
		cin >> a[i];
		Hash[a[i]] = 1;
	}
	for (int i = 1; i <= n; i++) {
		int m;
		cin >> m;
		while (m--) {
			int y;
			cin >> y;
			add(y, i);
			indeg[i]++;
			add2(i, y);
		}
	}
	topo();
	int cnt = 0;
	for (int i = 0; i < (int) v.size(); i++) {
		if (Hash[v[i]]) cnt++;
	}
	if (cnt < k) { cout << -1; return 0; }
	for (int i = 1; i <= k; i++) {
		if (!vis[a[i]]) dfs(a[i]);
	}
	cout << ans << '\n';
	for (int i = 0; i < (int) v.size(); i++) {
		if (vis[v[i]]) cout << v[i] << ' ';
	}
	return 0;
}