BZOJ原题链接

洛谷原题链接

和 Going from u to v or from v to u?（题解）这道题类似，只不过是求最大子图的大小和个数而已。

一样用\(tarjan\)求强连通分量，并进行缩点，然后对于缩点后的\(DAG\)进行拓扑排序\(DP\)。

定义\(size[i]\)表示缩点后的图中每个点（即强连通分量）包含原有的点数，\(f[i]\)表示最大子图（缩点后实际上是一条链）的大小，\(g[i]\)表示大小为\(f[i]\)的终点为\(i\)的子图个数。

设当前边为\((x,y)\)，则有转移方程：

\(\qquad\qquad g[y] = g[y] + g[x]\quad \mathrm{if}\ f[x] + size[y]=f[y]\)

\(\qquad\qquad g[y] = g[x],f[y]=f[x]+size[y]\quad \mathrm{if}\ f[x] + size[y]>f[y]\)

最后对拓扑排序\(DP\)后的\(f,g\)数组进行统计即可。

另外，在缩点时必须去重边，这里我用的是\(Hash\)去重，结果因为冲突调了一晚上。。非酋没办法。。

#include<cstdio>

#include<cstring>

#include<bitset>

using namespace std;

const int N = 1e5 + 10;

const int M = 1e6 + 10;

const int P = 1e8 - 11;

struct eg {

	int x, y;

};

eg a[M];

int fi[N], di[M], ne[M], cfi[N], cdi[M], cne[M], dfn[N], low[N], dis[N], sta[N], bl[N], ru[N], si[N], g[N], f[N], q[M], lc, l, tp, SCC, ti, mod;

bool v[N];

bitset<100000000>bs;

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline void add(int x, int y)

{

	di[++l] = y;

	ne[l] = fi[x];

	fi[x] = l;

}

inline void add_c(int x, int y)

{

	cdi[++lc] = y;

	cne[lc] = cfi[x];

	cfi[x] = lc;

}

inline int minn(int x, int y)

{

	return x < y ? x : y;

}

void tarjan(int x)

{

	int i, y;

	dfn[x] = low[x] = ++ti;

	sta[++tp] = x;

	v[x] = 1;

	for (i = fi[x]; i; i = ne[i])

		if (!dfn[y = di[i]])

		{

			tarjan(y);

			low[x] = minn(low[x], low[y]);

		}

		else

			if (v[y])

				low[x] = minn(low[x], dfn[y]);

	if (!(dfn[x] ^ low[x]))

	{

		SCC++;

		do

		{

			y = sta[tp--];

			bl[y] = SCC;

			v[y] = 0;

			si[SCC]++;

		} while (x ^ y);

	}

}

void topsort()

{

	int i, y, x, head = 0, tail = 0;

	for (i = 1; i <= SCC; i++)

		if (!ru[i])

		{

			q[++tail] = i;

			f[i] = si[i];

			g[i] = 1;

		}

	while (head ^ tail)

	{

		x = q[++head];

		for (i = cfi[x]; i; i = cne[i])

		{

			y = cdi[i];

			ru[y]--;

			if (!ru[y])

				q[++tail] = y;

			if (!((f[x] + si[y]) ^ f[y]))

				g[y] = (g[y] + g[x]) % mod;

			else

				if (f[x] + si[y] > f[y])

				{

					f[y] = f[x] + si[y];

					g[y] = g[x];

				}

		}

	}

}

int hs(int x, int y)

{

	return (12598LL * x + y) % P + 1;

}

int main()

{

	int i, n, m, x, y, k, S = 0, L;

	n = re();

	m = re();

	mod = re();

	for (i = 1; i <= m; i++)

	{

		a[i].x = re();

		a[i].y = re();

		add(a[i].x, a[i].y);

	}

	for (i = 1; i <= n; i++)

		if (!dfn[i])

			tarjan(i);

	for (i = 1; i <= m; i++)

	{

		x = bl[a[i].x];

		y = bl[a[i].y];

		if (x ^ y && !bs[k = hs(x, y)])

		{

			add_c(x, y);

			bs[k] = 1;

			ru[y]++;

		}

	}

	topsort();

	for (i = 1; i <= SCC; i++)

		if (S < f[i])

		{

			S = f[i];

			L = g[i];

		}

		else

			if (!(S ^ f[i]))

				L = (L + g[i]) % mod;

	printf("%d\n%d", S, L);

	return 0;

}