Description
定义一个半联通图为 : 对任意的两个点$u, v$,都有存在一条路径从$u$到$v$, 或从$v$到$u$。
给出一个有向图, 要求出节点最多的半联通子图, 并求出方案数。
Solution
先进行一次$Tarjan SCC$ 缩点, 得到一个有向无环图, 则半联通子图一定是一条单向的链。
然后就相当于求出最大的链的节点数, 以及有多少种链有这么多节点。
从每个入度为$0$ 的节点开始$DP$即可。 还需要注意同一对联通块的边需要判重。
Code
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define rd read() 6 using namespace std; 7 typedef pair<int, int> P; 8 9 const int N = 1e5 + 5; 10 const int M = 1e6 + 5; 11 12 int head[N], tot; 13 int Head[N], Tot; 14 int low[N], dfn[N], cnt, col, c[N], r[N], sz[N], inq[N], num[N], vis[N], sum[N]; 15 int st[N], tp; 16 int n, m, mod, ans1, ans2; 17 18 struct edge { 19 int nxt, to, fr; 20 }e[M], E[M]; 21 22 int read() 23 { 24 int X = 0, p = 1; char c = getchar(); 25 for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1; 26 for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0'; 27 return X * p; 28 } 29 30 void add(int u, int v) { 31 e[++tot].to = v; 32 e[tot].nxt = head[u]; 33 e[tot].fr = u; 34 head[u] = tot; 35 } 36 37 void Add(int u, int v) { 38 E[++Tot].to = v; 39 E[Tot].nxt = Head[u]; 40 Head[u] = Tot; 41 r[v]++; 42 } 43 44 void tarjan(int u) { 45 low[u] = dfn[u] = ++cnt; 46 st[++tp] = u; 47 inq[u] = 1; 48 for (int i = head[u]; i; i = e[i].nxt) { 49 int nt = e[i].to; 50 if (!dfn[nt]) tarjan(nt), low[u] = min(low[u], low[nt]); 51 else if (inq[nt]) low[u] = min(low[u], dfn[nt]); 52 } 53 if (dfn[u] == low[u]) { 54 col++; 55 for (;;) { 56 int now = st[tp--]; 57 c[now] = col; 58 inq[now] = 0; 59 sz[col]++; 60 if (now == u) 61 break; 62 } 63 } 64 } 65 66 void dp(int u) { 67 if (num[u]) return; 68 num[u] = 1; 69 sum[u] = sz[u]; 70 for (int i = Head[u]; i; i = E[i].nxt) { 71 int nt = E[i].to; 72 if (vis[nt] == u) 73 continue; 74 dp(nt); vis[nt] = u; 75 if (sum[nt] + sz[u] > sum[u]) 76 sum[u] = sum[nt] + sz[u], num[u] = num[nt]; 77 else if (sum[nt] + sz[u] == sum[u]) 78 num[u] = (num[u] + num[nt]) % mod; 79 } 80 } 81 82 int main() 83 { 84 n = rd; m = rd; mod = rd; 85 for (int i = 1; i <= m; ++i) { 86 int u = rd, v = rd; 87 add(u, v); 88 } 89 for (int i = 1; i <= n; ++i) 90 if (!dfn[i]) tarjan(i); 91 for (int i = 1; i <= tot; ++i) { 92 int u = e[i].fr, v = e[i].to; 93 if (c[u] == c[v]) 94 continue; 95 Add(c[u], c[v]); 96 } 97 for (int i = 1; i <= col; ++i) 98 if (!r[i]) dp(i); 99 for (int i = 1; i <= col; ++i) 100 ans1 = max(ans1, sum[i]); 101 for (int i = 1; i <= col; ++i) 102 if (ans1 == sum[i]) ans2 = (ans2 + num[i]) % mod; 103 printf("%d %d ", ans1, ans2); 104 }