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;
}