Acwing 1175.最大连通子图
题意
输入格式
第一行包含三个整数 N , M , X 。N,M 分别表示图 G 的点数与边数，X 的意义如上文所述;
接下来 M行，每行两个正整数 a,b ，表示一条有向边(a,b) 。
图中的每个点将编号为 1 到 N ，保证输入中同一个(a,b) 不会出现两次。
输出格式
应包含两行。
第一行包含一个整数 K KK ，第二行包含整数 C m o d X o
数据范围
思路
强连通分量必然是半连通
求解步骤：
先用tarjan算法求出强连通分量并缩点
建图 给边判重（给边判重的原因是 两个半连通子图不相同当且仅当两个子图有某些点不同 而当两个半连通子图只有边不同时，我们认为它们相等）
拓扑图上求最大半连通子图 ⟺ \iff⟺ 求最长无分叉链
求最长无分叉链 ⟺ \iff⟺ 拓扑图上的最长路（scc中点的数量为权重）
代码
// 题目给的 M 为 1e6 但是我们要建两个图 所以 设 M 为 2e6 const int N = 1e5 + 10, M = 2e6 + 10; int n, m, mod; int h[N],hs[N],e[M],ne[M],idx; int low[N],dfn[N]; int scc,timestamp; stack<int>stk; bool in_stk[N]; int id[N],siz[N]; int f[N],g[N]; unordered_set<LL>S; void add(int h[],int a,int b){ e[idx] = b,ne[idx] = h[a],h[a] = idx++; } void tarjan(int u){ dfn[u] = low[u] = ++timestamp; stk.push(u),in_stk[u] = true; 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(dfn[u] == low[u]){ int y = 0; ++scc; do{ y = stk.top(); stk.pop(); in_stk[y] = false; siz[scc]++; id[y] = scc; }while(y != u); } } void solve() { scanf("%d%d%d",&n,&m,&mod); memset(h,-1,sizeof h); memset(hs,-1,sizeof hs); while(m--){ int a,b;scanf("%d%d",&a,&b); add(h,a,b); } for(int i = 1;i <= n;++i){ if(!dfn[i]) tarjan(i); } for(int i = 1; i <= n;++i){ // 对scc建图 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 && !S.count(hash)){ add(hs,a,b); S.insert(hash); } } } for(int i = scc;i;--i){ // scc递减的顺序为 拓扑序 if(!f[i]){ f[i] = siz[i]; g[i] = 1; } for(int j = hs[i];~j;j = ne[j]){ int k = e[j]; if(f[k] < f[i] + siz[k]){ f[k] = f[i] + siz[k]; g[k] = g[i]; } else if(f[k] == f[i] + siz[k]){ g[k] = (g[k] + g[i]) % mod; } } } LL sum = 0,maxn = 0; for(int i = 1; i <= scc;++i){ if(f[i] > maxn){ maxn = f[i]; sum = g[i]; } else if(f[i] == maxn){ sum = (sum + g[i]) % mod; } } printf("%lld\n",maxn); printf("%lld\n",sum); } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
