【題目鏈接】

ybt 1514：【例 2】最大半連通子圖
洛谷 P2272 [ZJOI2007] 最大半連通子圖

【題目考點】

1. 圖論：強連通分量 縮點

2. 圖論：拓撲排序 有向無環圖動規

【解題思路】

對于圖中任意兩頂點u、v，滿足u到v或v到u有路徑，該圖就是單向連通圖。本題中的半連通圖，指的就是單向連通圖。
導出圖，指的是選擇頂點之間的所有邊也都必須選擇。
該題求圖中最大的半連通子圖，而且該圖必須是導出圖，也就是選擇頂點數最多的單向連通子圖，而且要同時選擇選出頂點之間所有的邊。
強連通圖一定是單向連通圖，因此可以不用考慮各個強連通分量內部的情況，可以將每個強連通分量視為一個頂點，進行縮點。縮點后，每個頂點(強連通分量)的權值是該強連通分量中頂點數量。
有向無環圖中的單向連通子圖中的頂點一定是圖中一條路徑上的頂點。

反證法：一條路徑上的頂點是$A_1,A_2,...,A_m$，假設存在頂點$B$，頂點$B$和頂點$A_1,A_2,...,A_m$不會構成一條路徑，$A_1,A_2,...,A_m,B$的導出圖是一個單向連通圖。

• 如果頂點$B$到頂點$A_1$有邊，則$B,A_1,A_2,...,A_m$是一條路徑，不符合假設。而該圖是單向連通圖，如果頂點$B$到頂點$A_1$沒有路徑，那么必然存在頂點$A_1$到頂點$B$的路徑。
• 如果頂點$B$到頂點$A_2$有邊，則$A_1,B,A_2,...,A_m$是一條路徑，不符合假設。而該圖是單向連通圖，如果頂點$B$到頂點$A_2$沒有路徑，那么必然存在頂點$A_2$到頂點$B$的路徑。
  …
• 依此類推，頂點$A_1$、$A_2$、…、$A_{m?1}$到頂點B都有路徑。
  如果頂點$A_m$到頂點$B$有邊，那么$A_1,A_2,...,A_m,B$是一條路徑，不符合假設。
  如果頂點$B$到頂點$A_m$有邊，那么$A_1,A_2,...,A_{m?1},B,A_m$是一條路徑，不符合假設。
  因此假設不成立，原命題得證。

在縮點后的圖中，找到點權加和最大的路徑，選擇該路徑上的頂點(強連通分量)在原圖中對應的頂點，以及這些頂點之間的邊構成的子圖，就是原圖中的最大半連通子圖。
縮點后圖中點權加和最大路徑的點權加和，就是原圖中最大半連通子圖包含的頂點數量。
而后還需要求最大半連通子圖的數量，這里可以通過統計點權和為最大路徑點權和的路徑數量，來統計半連通子圖的數量。
兩個連通分量中可能有多條邊相連，縮點后的圖中兩個頂點之間就可能有多條邊，即為重邊。如果縮點后的圖中保留重邊，假設頂點A到頂點B有兩條重邊，那么頂點A到頂點B會被認為有兩條路徑。而本題實際求的是半連通子圖的數量，半連通子圖必須是導出圖，這里選擇了頂點A和頂點B，那么頂點A、B之間的所有邊都必須被選擇，實際只有一個半連通子圖。為了使路徑數量和半連通子圖一致，本題必須
在縮點后的圖中去掉所有重邊，此處可以使用與離散化類似的方法完成對重邊去重。
接下來就是在縮點后的圖中，求有向無環圖中點權加和最大的路徑的點權加和，具體方法見該題：
信息學奧賽一本通 1262：【例9.6】挖地雷 | 洛谷 P2196 [NOIP1996 提高組] 挖地雷
$dp[i]$表示以頂點i為終點的點權加和最大的路徑的點權加和，在拓撲排序過程中可以求出$dp$數組的值。求$dp$數組最大值的下標為$mxi$，頂點$mxi$就是點權加和最大的路徑的終點。$dp[mxi]$就是第一個要輸出的解。

為了求出最大半連通子圖的數量，在拓撲排序時還需要進行另一個動規狀態求解：
狀態定義$cnt[i]$：以頂點i為終點的點權加和為最大值$dp[mxi]$的路徑的數量。
在拓撲排序過程中，在訪問u的鄰接點v時：

• 如果$dp[v]<dp[u]+w[v]$，($w[v]$是頂點v的點權)。那么要更新$dp[v]=dp[u]+w[v]$，經過頂點u再到頂點v的路徑的點權加和最大，到頂點v點權加和為$dp[v]$的路徑數量就是到頂點u點權加為$dp[u]$的路徑數量，也就是$cnt[v]=cnt[u]$
• 如果$dp[v]==dp[u]+w[v]$，那么$dp[v]$無需更新，但到達頂點v的點權加和為$dp[v]$的路徑增多了，增加了到達頂點u點權加為$dp[u]$的路徑數量，即$cnt[v]+=cnt[u]$，該題路徑數量需要對$X$取模，所以增加后應該再模X，寫為cnt[v] = (cnt[v]+cnt[u])%x

【題解代碼】

解法1：圖論 tarjan求強連通分量 縮點 拓撲排序DP

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n, m, x, dp[N], w[N], cnt[N], cntAns, dfn[N], low[N], ts, scc[N], sn, degIn[N], mxi = 1;
stack<int> stk;
bool inStk[N];
vector<int> edge[N], g[N];//edge：原圖 g：縮點后的圖
void tarjan(int u)
{int t;dfn[u] = low[u] = ++ts;stk.push(u);inStk[u] = true;for(int v : edge[u]){if(dfn[v] == 0){tarjan(v);low[u] = min(low[u], low[v]);}else if(inStk[v])low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){++sn;do{t = stk.top();stk.pop();inStk[t] = false;scc[t] = sn;w[sn]++;//連通分量sn中的頂點數，也就是縮點后頂點sn的權值w[sn]增加1 } while(t != u);}
}
void topoSort()
{queue<int> que;for(int i = 1; i <= sn; ++i){dp[i] = w[i];//dp[i]：縮點后以強連通分量i為終點的點權加和最大的路徑的點權加和cnt[i] = 1;if(degIn[i] == 0)que.push(i); }while(!que.empty()){int u = que.front();que.pop();if(dp[u] > dp[mxi])mxi = u;//mxi：某個以mxi為終點的路徑的點權加和最大 for(int v : g[u]){if(dp[v] < dp[u]+w[v]){dp[v] = dp[u]+w[v];cnt[v] = cnt[u];}else if(dp[v] == dp[u]+w[v])cnt[v] = (cnt[v]+cnt[u])%x;if(--degIn[v] == 0)que.push(v);}}
}
int main()
{int a, b;cin >> n >> m >> x;for(int i = 1; i <= m; ++i){cin >> a >> b;edge[a].push_back(b);}for(int i = 1; i <= n; ++i) if(dfn[i] == 0)tarjan(i);for(int u = 1; u <= n; ++u)for(int v : edge[u]) if(scc[v] != scc[u])g[scc[u]].push_back(scc[v]);for(int i = 1; i <= sn; ++i){sort(g[i].begin(), g[i].end());g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());//g[i]去重 }for(int u = 1; u <= sn; ++u)for(int v : g[u])degIn[v]++;//degIn[i]：縮點后強連通分量i的入度 topoSort();cout << dp[mxi] << '\n';for(int i = 1; i <= sn; ++i) if(dp[i] == dp[mxi])//所有以i為終點的，點權加和為dp[mxi]的路徑數量加和 cntAns = (cntAns+cnt[i])%x;cout << cntAns;return 0;
}