题目大意
题目是图片形式的，就简要说下题意算了
一个有向图 G=(V, E) 称为半连通的（Semi-Connected），如果满足图中任意两点 u v，存在一条从 u 到 v 的路径或者从 v 到 u 的路径
给一个有向图（n 个点，m 条边），求出她的最大半连通子图中所包含的点数，以及这样的最大半连通子图有多少个（要求模上一个给定的数 x）
对于20%的数据， N ≤18；
对于60%的数据， N ≤10000；
对于100%的数据， N ≤100000, M ≤1000000；
对于100%的数据， X ≤10^8。
做法分析
这种题目在 POJ 做过类似的：POJ 2762 Going from u to v or from v to u?，它只是询问一个图是否是半连通的，解题报告
这题其实也差不多的做法，先缩点，重新建图，使其成为一个 DAG，DAG 中每个点有一个点权表示这个点是原图中的几个点缩成的
新图中的一个最大半连通子图，必然是新图中的一个最长链（点权和最大），知道了这点之后，DP 就行了，类似于树形 DP，先求出从每个点出发，能走的最长链是多长，统计最长的那条就是最大半连通子图的点的数量了，至于怎么求有多少个最大半连通子图，也是一样的 DP 就行，在上一步的 DP 之后，再 DP 一遍，统计每个点出发能走出多少条最长链，最后统计求和即可
参考代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#include <vector>
#include <set> using namespace std; const int N=; set <pair<int, int> > tub;
stack <int> S;
vector <int> arc[N], adj[N];
int n, m, x, ans1, ans2, T, ind;
int id[N], low[N], dfn[N], cnt[N];
bool vs[N]; void tarjan(int u) {
dfn[u]=low[u]=T++;
S.push(u), vs[u]=;
for(int i=, len=(int)adj[u].size(); i<len; i++) {
int v=adj[u][i];
if(dfn[v]==-) {
tarjan(v);
if(low[u]>low[v]) low[u]=low[v];
}
else if(vs[v] && low[u]>dfn[v]) low[u]=dfn[v];
}
if(low[u]==dfn[u]) {
while() {
int v=S.top();
S.pop(), vs[v]=;
id[v]=ind, cnt[ind]++;
if(v==u) break;
}
ind++;
}
} void DFS1(int u) {
vs[u]=;
for(int i=, len=(int)arc[u].size(); i<len; i++) {
int v=arc[u][i];
if(!vs[v]) DFS1(v);
dfn[u]=max(dfn[u], dfn[v]);
}
dfn[u]+=cnt[u];
} void DFS2(int u) {
vs[u]=;
for(int i=, len=(int)arc[u].size(); i<len; i++) {
int v=arc[u][i];
if(!vs[v]) DFS2(v);
if(dfn[u]==cnt[u]+dfn[v]) id[u]=(id[u]+id[v])%x;
}
if((int)arc[u].size()==) id[u]=;
if(dfn[u]==ans1) ans2=(ans2+id[u])%x;
} int main() {
// freopen("in", "r", stdin);
scanf("%d%d%d", &n, &m, &x);
for(int i=; i<=n; i++) adj[i].clear();
for(int i=, a, b; i<m; i++) {
scanf("%d%d", &a, &b);
adj[a].push_back(b);
}
fill(dfn, dfn++n, -);
fill(vs, vs++n, );
T=ind=;
while(!S.empty()) S.pop();
for(int i=; i<=n; i++) if(dfn[i]==-) tarjan(i);
for(int i=; i<ind; i++) arc[i].clear();
fill(low, low+ind, );
tub.clear();
for(int i=; i<=n; i++)
for(int j=, len=(int)adj[i].size(); j<len; j++) {
int v=id[adj[i][j]], u=id[i];
if(u==v) continue;
if(tub.find(make_pair(u, v))!=tub.end()) continue;
low[v]++, arc[u].push_back(v);
tub.insert(make_pair(u, v));
}
fill(vs, vs+ind, );
fill(dfn, dfn+ind, );
ans1=, ans2=;
for(int i=; i<ind; i++) if(low[i]==) {
DFS1(i);
ans1=max(ans1, dfn[i]);
}
fill(vs, vs+ind, );
fill(id, id+ind, );
for(int i=; i<ind; i++) if(low[i]==) DFS2(i);
printf("%d\n%d\n", ans1, ans2);
return ;
}
BZOJ 1093
题目链接 & AC 通道