【题目描述】
原题来自:ZJOI 2007
一个有向图 G=(V,E)
称为半连通的 (Semi-Connected),如果满足:∀u,v∈V,满足 u→v或 v→u,即对于图中任意两点 u,v,存在一条 u 到 v 的有向路径或者从 v 到 u
的有向路径。
若 G'=(V',E')
满足,E' 是 E 中所有和V' 有关的边,则称G' 是 G 的一个导出子图。若 G' 是 G 的导出子图,且 G' 半连通,则称 G' 为 G 的半连通子图。若G' 是 G 所有半连通子图中包含节点数最多的,则称 G' 是 G
的最大半连通子图。
给定一个有向图 G
,请求出 G 的最大半连通子图拥有的节点数 K,以及不同的最大半连通子图的数目 C。由于 C 可能比较大,仅要求输出 C 对 X
的余数。
【输入】
第一行包含三个整数 N,M,X
。N,M 分别表示图 G 的点数与边数,X
的意义如上文所述;
接下来 M
行,每行两个正整数 a,b,表示一条有向边 (a,b
)。
图中的每个点将编号为 1,2,3,⋯,N
,保证输入中同一个 (a,b
)不会出现两次。
【输出】
应包含两行。第一行包含一个整数 K
,第二行包含整数CmodX
。
【输入样例】
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
【输出样例】
3
3
【提示】
对于 20% 的数据,N≤18
;
对于 60% 的数据,N≤104
;
对于 100% 的数据,1≤N≤105,1≤M≤106,X≤108
。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#pragma GCC optimize (2)
using namespace std;
#define ll long long
const int N = 100010, M = 2000010;
int dfn[N], low[N], timestamp;
int n, m, x;
int stk[N], in_stk[N], top;
int id[N], scc_cnt, scc_size[N];
int f[N], g[N];
int h[N], hs[N], w[M], ne[M], e[M], idx;
void add(int h[], int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void tarjan(int u) {
low[u] = dfn[u] = ++timestamp;
stk[++top] = u;
in_stk[u] = 1;
for (int i = h[u] ; ~i ; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
} else if (in_stk[j]) {
low[u] = min(low[u], dfn[j]);
}
}
if (low[u] == dfn[u]) {
++scc_cnt;
int y;
do {
y = stk[top--];
in_stk[y] = 0;
id[y] = scc_cnt;
scc_size[scc_cnt]++;
} while (y != u);
}
}
int main() {
memset(h, -1, sizeof(h));
memset(hs, -1, sizeof(hs));
scanf("%d %d %d", &n, &m, &x);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
add(h, a, b);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i])
tarjan(i);
}
map <ll, int> m;
m.clear();
for (int i = 1; i <= n; i++) {
for (int j = h[i]; ~j; j = ne[j]) {
int k = e[j];
int a = id[i], b = id[k];
ll hash = a * 1000000ll + b;
if (a != b && m[hash] == 0) {
add(hs, a, b);
m[hash] = 1;
}
}
}
for (int i = scc_cnt; i ; i--) {
if (!f[i]) {
f[i] = scc_size[i];
g[i] = 1;
}
for (int j = hs[i]; ~j ; j = ne[j]) {
int k = e[j];
if (f[k] < f[i] + scc_size[k]) {
f[k] = f[i] + scc_size[k];
g[k] = g[i];
} else if (f[k] == f[i] + scc_size[k]) {
g[k] = (g[k] + g[i]) % x;
}
}
}
int maxx = 0, sum = 0;
for (int i = 1; i <= scc_cnt; i++) {
if (f[i] > maxx) {
maxx = f[i];
sum = g[i];
} else if (f[i] == maxx) {
sum = (sum + g[i]) % x;
}
}
printf("%d\n%d", maxx, sum);
return 0;
}