21.11.16模拟 问题

你需要完成 n 道题目。有一些题目是相关的，当你做一道题的时候，如果你之前做过对它有帮助的题目，你会更容易地做出它。帮助关系具有传递性，如果题目 x 对题目 y 有帮助，题目 y 对题目 z 有帮助，那么题目x 对题目 z 也有帮助（尽管 x,z 可能不在输入中）。你可以自由安排做题的顺序。现在，你想要知道，你在完成所有题目的情况下，可能有多少道题目是在有帮助的情况下完成的。

缩点，然后可以缩成几条链。然后答案就是 n-强连通分量数 到 n-链数

const int N = 1e5 + 79;
const int M = 3e5 + 79;
struct graph {
	int head[N], tot, next[M], ver[M];
	inline void add(int a, int b) {
		ver[++tot] = b;
		next[tot] = head[a];
		head[a] = tot;
	}
} G, C;
int n, m;
int dfn[N], tim, low[N];
int s[N], top;
int ins[N], cnt;
int color[N], sum[N], r[N];
int in[N], ot[N], siz[N];
bool vis[N];
int t;
inline void  dfs(int x) {
	if(vis[x]) return;
	vis[x] = 1;
	++t;
	repc(x)
	dfs(C.ver[i]);
}

inline void tarjan(int x) {
	low[x] = dfn[x] = ++tim;
	s[++top] = x;
	ins[x] = 1;
	repg(x) {
		int y(G.ver[i]);
		if(!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		} else if(ins[y]) {
			low[x] = min(low[x], dfn[y]);
		}
	}
	if(low[x] == dfn[x]) {
		int y;
		++cnt;
		do {
			y = s[top--];
			++siz[cnt];
			ins[y] = 0;
			color[y] = cnt;
		} while(x != y);
	}
}
/*
2 1
1 2
0
1
*/


int main() {
	freopen("problem.in", "r", stdin);
	freopen("problem.out","w",stdout);
	read(n);
	read(m);
	int x, y;
	rep(i, 1, m) {
		read(x);
		read(y);
		G.add(x, y);
	}

	rep(i, 1, n) {
		if(!dfn[i]) {
			tarjan(i);
		}
	}
	rep(x, 1, n) {
		repg(x) {
			int y(G.ver[i]);
			if(color[y] == color[x]) continue;
			C.add(color[x], color[y]);
			++ot[color[x]];
			++in[color[y]];
		}
	}
	int k(0);
	rep(i, 1, cnt) {
		if(in[i]) continue;
		++k;
		dfs(i);
	}
	rep(i, n-t, n - k) {
		out(i, '\n');
	}
	return 0;
}