缩点后topo排序dp
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5,maxm=1e5+5; int n,m; int dq[maxn],ru[maxn],dis[maxn],a[maxm],b[maxm]; int dfn[maxn],low[maxn],vis[maxn],z[maxn],color[maxn],cnt[maxn],du[maxn],t,k,tot; vector<int>e[maxm]; vector<int>g[maxm]; void tarjan(int u){ dfn[u]=low[u]=++tot; z[++k]=u;//入栈 vis[u]=1; for(int i=0;i<e[u].size();i++){ if(!dfn[e[u][i]]){ tarjan(e[u][i]); low[u]=min(low[u],low[e[u][i]]); } else if(vis[e[u][i]]){ low[u]=min(low[u],dfn[e[u][i]]); } } if(low[u]==dfn[u]){ int y; while(y=z[k--]){ color[y]=u; //属于这个连通分量 cnt[t]++; //记录这个环中有多少个点 vis[y]=0; if(u==y)break; dq[u]+=dq[y]; } } } int topo(){ queue<int>q; for(int i=1;i<=n;i++){ if(color[i]==i&&!ru[i]){ q.push(i); dis[i]=dq[i]; } } while(!q.empty()){ int u=q.front(); q.pop(); for(int i=0;i<g[u].size();i++){ int v=g[u][i]; ru[v]--; dis[v]=max(dis[v],dis[u]+dq[v]); if(ru[v]==0){ q.push(v); } } } int res=0; for(int i=1;i<=n;i++){ res=max(res,dis[i]); } return res; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ scanf("%d",&dq[i]); } for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); a[i]=u; b[i]=v; } for(int i=1;i<=n;i++){ if(!dfn[i])tarjan(i); } for(int i=1;i<=m;i++){ int x=color[a[i]],y=color[b[i]]; if(x!=y){ g[x].push_back(y); ru[y]++; } } cout<<topo(); return 0; }缩点+割点模板
纯模板
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5,maxm=1e5+5; int n,m; int dfn[maxn],low[maxn],vis[maxn],z[maxn],color[maxn],cnt[maxn],du[maxn],t,k,tot; vector<int>e[maxm]; void tarjan(int u){ dfn[u]=low[u]=++tot; z[++k]=u;//入栈 vis[u]=1; for(int i=0;i<e[u].size();i++){ if(!dfn[e[u][i]]){ tarjan(e[u][i]); low[u]=min(low[u],low[e[u][i]]); } else if(vis[e[u][i]]){ low[u]=min(low[u],dfn[e[u][i]]); } } if(low[u]==dfn[u]){ t++;//连通分量的标号 do{ color[z[k]]=t; //属于这个连通分量 cnt[t]++; //记录这个环中有多少个点 vis[z[k]]=0; k--; //出栈 }while(u!=z[k+1]); } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); } for(int i=1;i<=n;i++){ if(!dfn[i])tarjan(i); } for(int i=1;i<=n;i++){ for(int j=0;j<e[i].size();j++){ if(color[i]!=color[e[i][j]])du[color[i]]++; } } int ans=0; for(int i=1;i<=t;i++){ if(cnt[i]>1)ans++; } cout<<ans; return 0; }kuangbin联通性专题t1
题目给出的夫妻和情侣都是双向边的该怎么办呢 一个很棒的思路：一种 男->女 连边，另外一一种 女->男 连边 然后缩点，如果在这对情侣在同一个强联通分量里面的话就有问题
#include<bits/stdc++.h> using namespace std; const int maxn=1e4+5,maxm=5e4+5; unordered_map<string,int>mp; int dfn[maxn],low[maxn],vis[maxn],z[maxn],color[maxn],cnt[maxn],t,k,tot; int n,m; vector<int>e[maxm]; string mb[maxn],mg[maxn]; void tarjan(int u){ dfn[u]=low[u]=++tot; z[++k]=u; vis[u]=1; for(int i=0;i<e[u].size();i++){ int v=e[u][i]; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ t++; do{ color[z[k]]=t; cnt[t]++; vis[z[k]]=0; k--; }while(u!=z[k+1]); } } int main(){ cin>>n; int cx=0; string s1,s2; for(int i=1;i<=n;i++){ cin>>s1>>s2; mp[s1]=i; mp[s2]=i+n; e[i].push_back(i+n); } cin>>m; for(int i=1;i<=m;i++){ cin>>s1>>s2; e[mp[s2]].push_back(mp[s1]); } for(int i=1;i<=n*2;i++){ if(!dfn[i])tarjan(i); } for(int i=1;i<=n;i++){ if(color[i]==color[i+n]){ printf("Unsafe\n"); } else printf("Safe\n"); } return 0; }这个题的题意硬是看了半天都没有看懂 如果有u到v的一条边的话称u和v为半联通，求最大的半联通子图 既然有有一条边就是半联通的话，那缩点自然也是半联通 先缩点 然后DAG上DP 因为tarjan缩点完自带逆拓扑序，所以直接倒着遍历就是拓扑序
dp时的转移：
if(ans[v]<ans[u]+cnt[v]){ ans[v]=ans[u]+cnt[v]; tiao[v]=tiao[u]; } else if(ans[v]==ans[u]+cnt[v]){ tiao[v]+=tiao[u]; tiao[v]%=mod; }完整代码：
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5,maxm=4e6+5; int dfn[maxn],low[maxn],vis[maxn],z[maxn],color[maxn],cnt[maxn],t,k,tot; int n,m,mod,ans[maxn],use[maxn],tiao[maxn]; vector<int>e[maxm]; int head[maxn]; struct edge{ int v,nex; }ee[maxm]; int bs; void add(int u,int v){ ee[++bs].v=v; ee[bs].nex=head[u]; head[u]=bs; } void tarjan(int u){ dfn[u]=low[u]=++tot; z[++k]=u; vis[u]=1; for(int i=0;i<e[u].size();i++){ int v=e[u][i]; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ t++; do{ color[z[k]]=t; cnt[t]++; vis[z[k]]=0; k--; }while(u!=z[k+1]); } } int main(){ cin>>n>>m>>mod; int u,v; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); e[u].push_back(v); } for(int i=1;i<=n;i++){ if(!dfn[i])tarjan(i); } for(int u=1;u<=n;u++){ ans[u]=cnt[u]; tiao[u]=1; for(int i=0;i<e[u].size();i++){ int v=e[u][i]; if(color[u]==color[v])continue; add(color[u],color[v]); } } for(int u=t;u>=1;u--){ for(int i=head[u];i;i=ee[i].nex){ int v=ee[i].v; if(use[v]==u)continue; use[v]=u; if(ans[v]<ans[u]+cnt[v]){ ans[v]=ans[u]+cnt[v]; tiao[v]=tiao[u]; } else if(ans[v]==ans[u]+cnt[v]){ tiao[v]+=tiao[u]; tiao[v]%=mod; } } } int mm=0; int tt=0; for(int i=1;i<=t;i++){ if(mm<ans[i]){ mm=ans[i]; tt=tiao[i]; } else if(mm==ans[i]){ tt+=tiao[i]; tt%=mod; } } cout<<mm<<endl<<tt; return 0; }这题需要分情况讨论 样例1： 可以看出点1是割点，然后我们分析样例的答案： Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)； 割点两边各取一个点
样例2： 图中1 2 3是割点，取法唯一 Case 2 的一组解为(4,5,6,7)。
样例3： 割点是4 6 10 来分析一下怎么样统计需要多少个救援点和有多少种安排法
当一个联通块里没有割点时候，例如一个环，只要安排两个救援点，这时候不管切断哪个点，其他点都能继续连通，方案数为 C n 2 \mathrm{C}_n^2 Cn2
if(c==0){ gs+=2; ans*=(ds-1)*ds/2; }当一个联通块里有一个割点，比如样例一：1 ,2，3，5，6这个联通块，就需要在里面选一个非割点的点作为救援点
if(c==1){ gs+=1; ans*=ds; }当一个联通块里有两个或者两个以上的割点，如样例3的4，5，6这个联通块，并不需要做任何处理，因为这两个以上个割点，在其他联通块已经把救援点处理好了，不管断哪个点都能互相联通
还有一个坑点就是一开始并没有给出点的数量，需要自己在输入过程中维护 还有%lld 惨痛RE 完整代码：
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+5,maxm=4e5+5; int dfn[maxn],low[maxn],vis[maxn],t,top,tot; int cut[maxn],n,m,head[maxn],len; struct edge{ int v,nex; }e[maxm]; inline void add(int u,int v){ e[++len].v=v; e[len].nex=head[u]; head[u]=len; } void tarjan(int u,int root){ int child=0; dfn[u]=low[u]=++tot; for(int i=head[u];i;i=e[i].nex){ int v=e[i].v; if(!dfn[v]){ tarjan(v,root); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]&&u!=root)cut[u]=1; if(u==root)child++; } low[u]=min(low[u],dfn[v]); } if(u==root&&child>=2){ cut[root]=1; } } int c,ds,color; void dfs(int u){ ds++; vis[u]=color; for(int i=head[u];i;i=e[i].nex){ int v=e[i].v; if(cut[v]&&vis[v]!=color){ vis[v]=color; c++; } if(vis[v]==0)dfs(v); } return; } void init(){ memset(head,0,sizeof head); memset(dfn,0,sizeof dfn); memset(cut,0,sizeof cut); memset(vis,0,sizeof vis); memset(low,0,sizeof low); color=0; len=0,t=0,top=0,tot=0; } signed main(){ int tt=1; while(scanf("%lld",&n),n){ init(); int zdd=0; long long ans=1; long long gs=0; int u,v; for(int i=1;i<=n;i++){ scanf("%lld%lld",&u,&v); add(u,v); add(v,u); zdd=max(zdd,u); zdd=max(zdd,v); } for(int i=1;i<=zdd;i++){ if(!dfn[i])tarjan(i,i); } for(int i=1;i<=zdd;i++){ if(vis[i]==0&&cut[i]==0){ ds=0; c=0; color++; dfs(i); if(c==1){ gs+=1; ans*=ds; } if(c==0){ gs+=2; ans*=(ds-1)*ds/2; } } } printf("Case %lld: %lld %lld\n",tt++,gs,ans); } return 0; }这个题其实比较套路 读懂题之后发现是要找到一个割点，让st和ed在两边，且编号最小 要怎么实现st和ed在两边呢？ 直接拿st建树来求割点，找到割点后，判断ed的dfn是否大于等于割点u所连点v，如果符合，st和ed就必定是在割点的两边，直接在tarjan的过程中特判一下就好
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+5,maxm=1e6+5; int dfn[maxn],low[maxn],vis[maxn],z[maxn],color[maxn],cnt[maxn],t,top,tot; int cut[maxn],n,m,head[maxn],len,st,ed; struct edge{ int v,nex; }e[maxm]; inline void add(int u,int v){ e[++len].v=v; e[len].nex=head[u]; head[u]=len; } void tarjan(int u,int root){ int child=0; dfn[u]=low[u]=++tot; z[++top]=u; for(int i=head[u];i;i=e[i].nex){ int v=e[i].v; if(!dfn[v]){ tarjan(v,root); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]&&u!=root&&dfn[ed]>=dfn[v])cut[u]=1; if(u==root)child++; } low[u]=min(low[u],dfn[v]); } if(u==root&&child>=2){ cut[root]=1; } } int main(){ cin>>n; int u,v; while(scanf("%d%d",&u,&v),u+v){ add(u,v); add(v,u); } scanf("%d%d",&st,&ed); tarjan(st,st); for(int i=1;i<=n;i++){ if(cut[i]&&i!=st){ cout<<i; return 0; } } printf("No solution"); return 0; }树形DP还没学会，先咕咕咕
