一个有向图 \(G = (V,E)\) 称为半连通的 (Semi-Connected),如果满足:\(\forall u,v \in V\),满足 \(u \to v\) 或 \(v \to 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\) 到 \(N\),保证输入中同一个 \((a,b)\) 不会出现两次。
应包含两行。
第一行包含一个整数 \(K\),第二行包含整数 \(C \ mod\ X\)。
\(1 \le N \le 10^5\),
\(1 \le M \le 10^6\),
\(1 \le X \le 10^8\)
6 6 20070603 1 2 2 1 1 3 2 4 5 6 6 4
3 3
缩点,dag上dp
如果选择的最大半连通子图的一个点在强连通分量上,则该强连通分量都应该选上,故需要缩点,另外注意新建的图不能有重复边,需要特判,\(dfs\) 的逆序即拓扑序,所以缩点后的 \(scc_cnt\) 的逆序即为拓扑序,然后 \(dag\) 上 \(dp\):
状态表示:
时间复杂度:\(O(n+m)\)
// Problem: 最大半连通子图 // Contest: AcWing // URL: https://www.acwing.com/problem/content/1177/ // Memory Limit: 64 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> // #define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int N=1e5+5; int n,m,x,f[N],g[N]; vector<int> adj[N][2]; int dfn[N],low[N],id[N],sz[N],timestamp,stk[N],top,scc_cnt; bool in_stk[N]; set<PII> s; void tarjan(int x) { dfn[x]=low[x]=++timestamp; stk[++top]=x,in_stk[x]=true; for(int y:adj[x][0]) { if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(in_stk[y])low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]) { int y; scc_cnt++; do { y=stk[top--]; in_stk[y]=false; id[y]=scc_cnt; sz[scc_cnt]++; }while(y!=x); } } int main() { cin>>n>>m>>x; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; adj[x][0].pb(y); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=n;i++) for(int j:adj[i][0]) if(id[i]!=id[j]&&!s.count({id[i],id[j]})) adj[id[i]][1].pb(id[j]),s.insert({id[i],id[j]}); for(int i=scc_cnt;i;i--) { if(!f[i]) { f[i]=sz[i]; g[i]=1%x; } for(int j:adj[i][1]) { if(f[j]<f[i]+sz[j]) { f[j]=f[i]+sz[j]; g[j]=g[i]%x; } else if(f[j]==f[i]+sz[j]) g[j]=(g[j]+g[i])%x; } } int mx=0,sum=0; for(int i=1;i<=scc_cnt;i++) if(mx<f[i]) { mx=f[i]; sum=g[i]; } else if(mx==f[i]) sum=(sum+g[i])%x; cout<<mx<<'\n'<<sum<<'\n'; return 0; }