缩点 #dp #POI #Year2006

建反图， \(tarjan\) 缩点，在有向无环图上跑 \(topsort\)，\(dp\) 计算方案数

超过 \(36500\) 的直接与 \(36501\) 取 \(min\) 就可以避免炸 \(long\ long\)

特判

• 最大方案数为从最后一个点的强联通出发
• 最后一个点有自环

```cpp
// Author: xiaruize
#ifndef ONLINE_JUDGE
#define debug(x) cerr << "On Line:" << __LINE__ << #x << "=" << x << endl
bool start_of_memory_use;
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)

{
	if (a > b)
		return a;
	return b;
}
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e6 + 10;

int n, m;
vector<int> g[N], f[N];
pii eg[N];
int dfn[N], low[N], siz[N];
int col[N], tot, cnt;
stack<int> st;
bool vis[N];
bool sta[N];
int deg[N], dp[N];

void tarjan(int x)
{
	dfn[x] = low[x] = ++tot;
	st.push(x);
	vis[x] = true;
	for (auto v : g[x])
	{
		if (!dfn[v])
		{
			tarjan(v);
			low[x] = min(low[x], low[v]);
		}
		else if (vis[v])
			low[x] = min(low[x], dfn[v]);
	}
	if (low[x] == dfn[x])
	{
		cnt++;
		while (st.top() != x)
		{
			col[st.top()] = cnt;
			vis[st.top()] = false;
			siz[cnt]++;
			st.pop();
		}
		siz[cnt]++;
		vis[st.top()] = false;
		col[st.top()] = cnt;
		st.pop();
	}
}

void solve()
{
	cin >> n >> m;
	n++;
	rep(i, 1, m)
	{
		cin >> eg[i].first >> eg[i].second;
		g[eg[i].second].push_back(eg[i].first);
	}
	rep(i, 1, n) if (!dfn[i]) tarjan(i);
	rep(i, 1, m)
	{
		auto [u, v] = eg[i];
		if (col[u] == col[v])
			sta[col[u]] = true;
		else
		{
			f[col[v]].push_back(col[u]);
			deg[col[u]]++;
		}
	}
	queue<int> q;
	rep(i, 1, cnt) if (!deg[i]) q.push(i);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		if (x == col[n])
			continue;
		for (auto v : f[x])
		{
			deg[v]--;
			if (!deg[v])
				q.push(v);
		}
	}
	q.push(col[n]);
	dp[col[n]] = 1;
	while (!q.empty())
	{
		auto x = q.front();
		q.pop();
		if (sta[x])
			dp[x] = 36501;
		for (auto v : f[x])
		{
			deg[v]--;
			dp[v] += dp[x];
			dp[v] = min(dp[v], 36501);
			if (!deg[v])
				q.push(v);
		}
	}
	int mx = 0;
	rep(i, 1, cnt)
	{
		mx = max(mx, dp[i]);
	}
	if (mx > 36500)
		cout << "zawsze" << endl;
	else
		cout << mx << endl;
	int res = 0;
	rep(i, 1, cnt) if (dp[i] == mx) res += siz[i];
	cout << res - (mx == dp[col[n]]) << endl;
	rep(i, 1, n - 1)
	{
		if (dp[col[i]] == mx)
			cout << i << ' ';
	}
	cout << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}