对于一个有向图，连通分量：对于分量中任意两点u,v，必然可以从u到v，从v到u
强连通分量：最大连通分量
作用：将任意一个有向图缩点（将所有连通分量缩成一个点）变成有向无环图（拓扑图）
tarjan模板
void tarjan(int u) { dfn[u]=low[u]===timestamp; stk[++top]=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; ++scc_cnt;//连通分量的个数 do { y=stk[top--]; in_stk[y]=false; id[y]=scc_cnt; }while(y!=u); } }
缩点（把强连通分量缩成一个点）
一般做法：
1.tarjan
2.缩点
3.拓扑序递归求解
1.受欢迎的牛
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
1.tarjan
2.缩点
3.枚举求答案
当操作了tarjan和缩点之后变成的拓扑图，假如有两个出度为0的点说明，这两个点互不可达，说明没有一头牛受任何牛欢迎
假如有一个出度为0的点，说明这个点就是受所有牛欢迎的
假如只有一个连通分量说明连通分量里的每头牛都互相受欢迎，则+连通分量牛的数量
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e4+10,M=5e4+10; int n,m; int h[N],e[M],ne[M],idx; int dfn[N],low[N],timestamp;//dfn是第一次遍历的时间戳，low是以当前点往下走的最早的时间戳 int stk[N],top; bool in_stk[N];//标记是否在栈中 int id[N],scc_cnt,size[N];//id表示每个点属于强连通分量那个编号，scc_cnt表示强连通分量的个数，size表示每个强连通分量点的数量 int dout[N];//记录每个缩完点之后的出度是多少 void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u) { low[u]=dfn[u]=++timestamp;//让他们都等于时间戳 stk[++top]=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]) { ++scc_cnt;//连通分量++ int y; do { y=stk[top--]; in_stk[y]=false;//不在栈中 id[y]=scc_cnt;//让这个点的编号等于这个连通分量 size[scc_cnt]++;//这个连通分量数量++ }while(y!=u); } } int main() { memset(h,-1,sizeof h); cin>>n>>m; while(m--) { int a,b; cin>>a>>b; add(a,b); } for(int i=1;i<=n;i++)//tarjan求强连通分量 if(!dfn[i])//假如没有遍历过 tarjan(i); for(int u=1;u<=n;u++)//缩点 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; int a=id[u],b=id[j]; if(a!=b) dout[a]++;//假如不在一个连通分量里，则a在的连通分量出度++ } int zeros=0,sum=0; for(int i=1;i<=scc_cnt;i++) if(!dout[i]) { zeros++; sum+=size[i];//假如连通分量的个数 if(zeros>1)//假如有多个连通分量的出度等于0，说明没有任何一头牛受欢迎 { sum=0; break; } } cout<<sum<<endl; return 0; }
2.学校网络
367. 学校网络 - AcWing题库
1.tarjan
2.缩点
3.求入度与出度
入度为0的点是起点，出度为0的点是终点
最少给的软件就是给起点
建立的关系就起点与终点的最大值证明如下：
设起点为n个，终点有m个，并且设n<=m
1.当n==1时，直接把所有终点与起点相连就是所有都连通了则为m
2.当n>1时，我们可以让一个终点与起点相连，这样终点与起点都-1，直到起点只有1个时，我们已经连了n-1对起点与终点，此时起点只有一个，终点变成m-(n-1)个，这是根据1情况要连m-(n-1)个，加上刚刚连的n-1条起点与终点，则总的连接为m-(n-1)+(n-1)=m条证毕
当n>m也同理可证
#include<bits/stdc++.h> using namespace std; const int N=110,M=N*N; int n; int h[N],e[M],ne[M],idx; int dfn[N],low[N],timestamp; int stk[N],top; bool in_stk[N]; int id[N],scc_cnt; int din[N],dout[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u) { low[u]=dfn[u]=++timestamp;//获取这个位置的时间戳 stk[++top]=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(low[u]==dfn[u])//假如搜索到头了 { ++scc_cnt;//则最大强连通数量++ int y; do { y=stk[top--];//取出栈顶 in_stk[y]=false;//标记不在栈中了 id[y]=scc_cnt;//让这个点归到强这个强连通分支中 }while(y!=u); } } int main() { memset(h,-1,sizeof h); cin>>n; for(int i=1;i<=n;i++) { int t; while(cin>>t,t) { add(i,t); } } for(int i=1;i<=n;i++) if(!dfn[i])//假如还没搜索过 tarjan(i); for(int u=1;u<=n;u++)//枚举缩点后的 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; int a=id[u],b=id[j];//获取两个分别所在的强连通分量中 if(a!=b) dout[a]++,din[b]++;//让a出度++，b入度++ } int in=0,out=0; for(int i=1;i<=scc_cnt;i++)//分别获取起点与终点，也就是入度为0的点与出度为0的点 { if(!din[i]) in++;//入度为0是起点 if(!dout[i]) out++;//出度为0是终点 } cout<<in<<endl;//输出起点的数就是需要分发的个数 if(scc_cnt==1) puts("0");//假如只有一个强连通分支说明没有终点 else cout<<max(in,out)<<endl;//否则输出二者最大的数 return 0; }
3.最大半连通子图
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
1.tarjan
2.缩点判重
3.按照拓扑序递推
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10,M=2e6+10; int h[N],hs[N],e[M],ne[M],idx;//h是原来的图，hs是缩点后建的图 int dfn[N],low[N],timestamp; int stk[N],top; bool in_stk[N]; int id[N],scc_cnt,size[N];//size记录每个最大连通分量的数量 int f[N],g[N];//f是点的个数，g是方案数 int n,m,mod; unordered_set<ll> ha;//用来判重 void add(int h[],int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u)//用tarjan搜索强连通分量 { dfn[u]=low[u]=++timestamp; stk[++top]=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]) { ++scc_cnt; int y; do { y=stk[top--]; in_stk[y]=false; size[scc_cnt]++;//该强连通分量个数加1 id[y]=scc_cnt; }while(y!=u); } } int main() { memset(h,-1,sizeof h); memset(hs,-1,sizeof hs); scanf("%d%d%d",&n,&m,&mod); while(m--) { int a,b; scanf("%d%d",&a,&b); add(h,a,b); } for(int i=1;i<=n;i++)//跑一遍tarjan合并强连通分量 if(!dfn[i]) tarjan(i); for(int u=1;u<=n;u++)//建缩了点后的图 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; int a=id[u],b=id[j]; ll temp=a*1000000ll+b; if(a!=b&&!ha.count(temp))//假如不在一个连通分量里和避免重复建边 { add(hs,a,b); ha.insert(temp); } } //跑完tarjan得到的强连通分量就是一个拓扑序 for(int u=scc_cnt;u;u--)//从大到小就是拓扑序 { if(!f[u]) f[u]=size[u],g[u]=1;//假如这个点没有点，则让这个f等于该连通分量的数，方案就自己一个 for(int i=hs[u];~i;i=ne[i])//枚举所有与他相连的强连通分量 { int j=e[i]; if(f[u]+size[j]>f[j])//假如其他点的个数比我大，则更新 { f[j]=f[u]+size[j];//更新最大值 g[j]=g[u];//方案数等于他的方案数 } else if(f[u]+size[j]==f[j]) g[j]=(g[j]+g[u])%mod;//假如相等，则加上这个方案数 } } int maxf=0,sum=0; for(int i=1;i<=scc_cnt;i++)//求最多的点的方案数 if(f[i]>maxf) maxf=f[i],sum=g[i]; else if(f[i]==maxf) sum=(sum+g[i])%mod; printf("%d\n%d\n",maxf,sum);//输出最多的点和其方案数 return 0; }
4.银河
这题跟糖果那一题一样，但是用差分约束解决的spfa会被卡掉，所以用最大连通分量保证o(n+m)不会被卡
1.tarjan
2.缩点
3.依据拓扑序递推
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10,M=6e6+10; int n,m; int h[N],hs[N],e[M],ne[M],w[M],idx; int dfn[N],low[N],timestamp; int stk[N],top; bool in_stk[N]; int id[N],scc_cnt,sizes[N]; int dist[N]; void add(int h[],int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void tarjan(int u)//常规的tarjan模板 { dfn[u]=low[u]=++timestamp; stk[++top]=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(low[u]==dfn[u]) { ++scc_cnt; int y; do { y=stk[top--]; in_stk[y]=false; id[y]=scc_cnt; sizes[scc_cnt]++; }while(y!=u); } } int main() { memset(h,-1,sizeof h); memset(hs,-1,sizeof hs); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) add(h,0,i,1);//保证所有数都是大于1的 while(m--) { int t,a,b; scanf("%d%d%d",&t,&a,&b); if(t==1) add(h,a,b,0),add(h,b,a,0); else if(t==2) add(h,a,b,1); else if(t==3) add(h,b,a,0); else if(t==4) add(h,b,a,1); else add(h,a,b,0); } tarjan(0);//因为0号点跟所有点都连了边所以不用枚举其他点了 bool f=true;//判断是否有环 for(int u=0;u<=n;u++) { for(int i=h[u];~i;i=ne[i]) { int j=e[i]; int a=id[u],b=id[j]; if(a==b)//一个环中，也就是一个连通分量中 { if(w[i]>0)//最大连通量里的边权大于1，说明有正环 { f=false; break; } } else add(hs,a,b,w[i]);//反之其他连通分量建边就是拓扑序 } if(!f) break; } if(!f) puts("-1"); else { for(int u=scc_cnt;u;u--)//按照从大到小就是拓扑序 for(int i=hs[u];~i;i=ne[i]) { int j=e[i]; dist[j]=max(dist[j],dist[u]+w[i]);//更新每个点的距离最大值 } ll res=0; for(int i=1;i<=scc_cnt;i++) res+=(ll)dist[i]*sizes[i];//最大距离就是该点的距离乘以点数 printf("%lld\n",res); } return 0; }
