>Link

luogu P2272

ybtoj最大半连通子图

---

>Description

N ≤ 1 0 5 , M ≤ 1 0 6 N\le10^5,M\le10^6 N≤105,M≤106

---

>解题思路

强连通子图一定是半连通子图，所以考虑到把这张图进行缩点
然后图就变成了一个DAG
这时就会发现，题目要求求的最大半连通子图其实就是DAG上的一条链（如果是两条链组合的话，不满足要求）
要注意的是，缩点以后建边要注意判重，建重边的话会似的方案数变大！！

---

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#define N 1000010
#define LL long long
using namespace std;

map<int, bool> use[N];
queue<int> Q;
stack<int> st;
struct edge
{
	int to, nxt;
} e[N], ee[N];
int n, m, h[N], hh[N], cnt, cntt, tot, dfn[N], low[N];
int col[N], totcol, sum[N], d[N], f[N], ans1;
LL Mod, ans2, ff[N];

void dfs (int now)
{
	st.push (now);
	dfn[now] = low[now] = ++tot;
	int v;
	for (int i = h[now]; i; i = e[i].nxt)
	{
		v = e[i].to;
		if (!dfn[v])
		{
			dfs (v);
			low[now] = min (low[now], low[v]);
		}
		else if (!col[v])
		  low[now] = min (low[now], low[v]);
	}
	if (dfn[now] == low[now])
	{
		col[now] = ++totcol;
		sum[totcol] = 1;
		while (!st.empty() && st.top() != now)
		{
			col[st.top()] = totcol;
			sum[totcol]++;
			st.pop();
		}
		st.pop();
	}
}

int main()
{
	scanf ("%d%d%lld", &n, &m, &Mod);
	int u, v;
	for (int i = 1; i <= m; i++)
	{
		scanf ("%d%d", &u, &v);
		e[++cnt] = (edge){v, h[u]}; h[u] = cnt;
	}
	for (int i = 1; i <= n; i++)
	  if (!dfn[i]) dfs (i);
	for (int i = 1; i <= n; i++)
	  for (int j = h[i]; j; j = e[j].nxt)
	  {
	  	u = col[i], v = col[e[j].to];
	  	if (u == v || use[v][u]) continue;
	  	use[v][u] = 1;
	  	d[v]++;
	  	ee[++cntt] = (edge){v, hh[u]}; hh[u] = cntt;
	  }
	for (int i = 1; i <= totcol; i++)
	  if (!d[i])
	  {
	  	f[i] = sum[i], ff[i] = 1;
	  	Q.push (i);
	  }
	while (!Q.empty())
	{
		u = Q.front();
		Q.pop();
		for (int i = hh[u]; i; i = ee[i].nxt)
		{
			v = ee[i].to;
			d[v]--;
			if (f[u] + sum[v] == f[v])
			  ff[v] = (ff[v] + ff[u]) % Mod;
			else if (f[u] + sum[v] > f[v])
			  f[v] = f[u] + sum[v], ff[v] = ff[u];
			if (!d[v]) Q.push (v);
		}
	}
	for (int i = 1; i <= totcol; i++)
	  if (f[i] == ans1) ans2 = (ans2 + ff[i]) % Mod;
	  else if (f[i] > ans1) ans1 = f[i], ans2 = ff[i];
	printf ("%d\n%lld", ans1, ans2);
	return 0;
}