$Tarjan$缩点
Tarjan的第二个应用就是求缩点啦。缩点虽然比割点麻烦一点，但是用处也比割点要大不少。
本来要学另外两个缩点算法的,但是似乎没什么用...$MST$里确实有只能有$prim$或者只能用$kruscal$的题目，但是这三种缩点...在网上没有找到介绍它们之间作用差异的文章,可能真的没有什么区别吧.
缩点是对于有向图来说的。首先什么是强连通分量：里面的点两两之间互相可达。如果一道题中互相可达的点有某种神秘的联系(一个强连通分量等价于一个点的作用)时，就可以进行缩点。那么缩点有什么好处呢，显而易见的是可以快，把一些等价的点的操作一起做了，还有一个就是缩完点之后的图必然是一个$Dag$，可以在上面跑一些拓扑排序啊，$dp$啊之类的东西。
首先先看一个模板吧：
缩点：
题意概述：缩点后跑dp，求点权最大的路径，每个点的点权只算一次；
1 # include2 # include 3 # define R register int 4 5 using namespace std; 6 7 int H,k,bp,cnt,h,Top=0,n,m,x,y,a[10009],firs[10009],Firs[10009],sta[10009]; 8 int id[10009],low[10009],vis[10009],A[10009]; 9 int dp[10009],color[10009],r[10009],q[100009]; 10 struct edge 11 { 12 int too,nex; 13 }g[100009],G[100009]; 14 15 void add1(int x,int y) 16 { 17 g[++h].too=y; 18 g[h].nex=firs[x]; 19 firs[x]=h; 20 } 21 22 void add2(int x,int y) 23 { 24 G[++H].too=y; 25 G[H].nex=Firs[x]; 26 Firs[x]=H; 27 } 28 29 void dfs(int x) 30 { 31 low[x]=id[x]=++cnt; 32 vis[x]=1; 33 sta[++Top]=x; 34 int j; 35 for (R i=firs[x];i;i=g[i].nex) 36 { 37 j=g[i].too; 38 if(!id[j]) 39 { 40 dfs(j); 41 low[x]=min(low[x],low[j]); 42 } 43 else 44 { 45 if(vis[j]) low[x]=min(low[x],low[j]); 46 } 47 } 48 if(id[x]==low[x]) 49 { 50 bp++; 51 color[x]=bp; 52 A[bp]+=a[x]; 53 vis[x]=0; 54 while (sta[Top]!=x) 55 { 56 color[ sta[Top] ]=bp; 57 A[bp]+=a[ sta[Top] ]; 58 vis[ sta[Top] ]=0; 59 Top--; 60 } 61 Top--; 62 } 63 } 64 65 int main() 66 { 67 scanf("%d%d",&n,&m); 68 for (R i=1;i<=n;++i) 69 scanf("%d",&a[i]); 70 for (R i=1;i<=m;++i) 71 { 72 scanf("%d%d",&x,&y); 73 add1(x,y); 74 } 75 for (R i=1;i<=n;++i) 76 if(!id[i]) dfs(i); 77 for (R i=1;i<=n;++i) 78 for (R j=firs[i];j;j=g[j].nex) 79 { 80 k=g[j].too; 81 if(color[i]!=color[k]) add2(color[i],color[k]),r[ color[k] ]++; 82 } 83 int num=0; 84 for (R i=1;i<=bp;++i) 85 if(!r[i]) q[++num]=i,dp[i]=A[i]; 86 for (R i=1;i<=num;++i) 87 { 88 for (R j=Firs[ q[i] ];j;j=G[j].nex) 89 { 90 k=G[j].too; 91 r[k]--; 92 dp[k]=max(dp[k],dp[ q[i] ]+A[k]); 93 if(!r[k]) q[++num]=k; 94 } 95 } 96 int ans=dp[1]; 97 for (R i=2;i<=bp;i++) 98 ans=max(ans,dp[i]); 99 cout<
牛的舞会：
题意概述：找到大小大于1的强连通分量个数。
板子题*2，再开一个数组记录每个连通分量的大小就行啦。
1 # include2 # include 3 # define R register int 4 5 using namespace std; 6 7 const int maxn=10009; 8 int num=0,x,y,h,n,m; 9 int Ans=0,ans[maxn],cnt=0,Top=0,color[maxn],sta[maxn],vis[maxn],id[maxn],low[maxn],firs[maxn];10 struct edge11 {12 int too,nex;13 }g[50009];14 15 inline void add(int x,int y)16 {17 g[++h].too=y;18 g[h].nex=firs[x];19 firs[x]=h;20 }21 22 inline void dfs(int x)23 {24 id[x]=low[x]=++cnt;25 vis[x]=true;26 sta[++Top]=x;27 int j;28 for (R i=firs[x];i;i=g[i].nex)29 {30 j=g[i].too;31 if(!id[j])32 {33 dfs(j);34 low[x]=min(low[x],low[j]);35 }36 else37 {38 if(vis[j])39 low[x]=min(low[x],low[j]);40 }41 }42 if(id[x]==low[x])43 {44 color[x]=++num;45 vis[x]==0;46 while (sta[Top]!=x)47 {48 color[ sta[Top] ]=num;49 vis[ sta[Top] ]=0;50 Top--;51 }52 Top--;53 }54 }55 56 int main()57 {58 scanf("%d%d",&n,&m);59 for (R i=1;i<=m;++i)60 {61 scanf("%d%d",&x,&y);62 add(x,y);63 }64 for (R i=1;i<=n;++i)65 if(!id[i]) dfs(i);66 for (R i=1;i<=n;++i)67 ans[ color[i] ]++;68 for (R i=1;i<=n;++i)69 if(ans[i]>1) Ans++;70 cout<
受欢迎的牛：
题意概述：求图中某种点的个数（其余所有的点都可以通过某些路径到达它这里的点）。
因为路径可以绕来绕去，所以一个强连通分量里的点要么全是这种点，要么全都不是。如果一个强连通分量有出边，它必然不是一个受欢迎的强连通分量（它连出去的边一定没有连回来，否则就合成同一个连通分量了）。也就是说，找到唯一一个出度为$0$的强连通分量，它的大小就是答案。如果有不止一个这样的分量，说明图不连通，答案为$0$。
1 # include2 # include 3 # define R register int 4 5 using namespace std; 6 7 int n,m,h,x,y,firs[10009],a[10009]; 8 int id[10009],low[10009],vis[10009],sta[10009]; 9 int color[10009],cnt,bp,Top;10 int c[10009];11 struct edge12 {13 int too,nex;14 }g[50009];15 16 void add(int x,int y)17 {18 g[++h].too=y;19 g[h].nex=firs[x];20 firs[x]=h;21 }22 23 void dfs(int x)24 {25 id[x]=low[x]=++cnt;26 vis[x]=true;27 sta[++Top]=x;28 int j;29 for (R i=firs[x];i;i=g[i].nex)30 {31 j=g[i].too;32 if(!id[j])33 {34 dfs(j);35 low[x]=min(low[x],low[j]);36 }37 else38 {39 if(vis[j])40 low[x]=min(low[x],low[j]);41 }42 }43 if(low[x]==id[x])44 {45 color[x]=++bp;46 a[bp]++;47 vis[x]=0;48 while (sta[Top]!=x)49 {50 color[ sta[Top] ]=bp;51 a[bp]++;52 vis[ sta[Top] ]=0;53 Top--;54 }55 Top--;56 }57 }58 59 int main()60 {61 scanf("%d%d",&n,&m);62 for (R i=1;i<=m;++i)63 {64 scanf("%d%d",&x,&y);65 add(x,y);66 }67 for (R i=1;i<=n;++i)68 if(!id[i]) dfs(i);69 for (R i=1;i<=n;++i)70 for (R j=firs[i];j;j=g[j].nex)71 {72 if(color[i]!=color[ g[j].too ])73 c[ color[ i ] ]++; 74 }75 int ans=0;76 for (R i=1;i<=bp;++i)77 {78 if(c[i]==0) 79 {80 if(ans==0) ans=a[i];81 else82 {83 printf("0");84 return 0;85 }86 }87 }88 printf("%d",ans);89 return 0;90 }
在农场万圣节：
题意概述：给定一张有向图，求从每个点出发路过的点的个数。（每个点的后继唯一，不能走重复点）。
看起来缩点非常可行，且走进一个分量就出不来了，所以缩点后进行记忆化搜索就可以啦。这道题有一个简化的地方，每个点只有单一的后继，所以不用前向星，只用一个$nex$数组也是完全可以的。
1 # include2 # include 3 # define R register int 4 5 using namespace std; 6 7 const int maxn=100009; 8 int n,cnt,bp,Top; 9 int nex[maxn],vis[maxn],A[maxn],dp[maxn];10 int low[maxn],id[maxn],sta[maxn],color[maxn];11 int Nex[maxn],touc[maxn];12 13 void dfs(int x)14 {15 id[x]=low[x]=++cnt;16 vis[x]=1;17 sta[++Top]=x;18 if(!id[ nex[x] ])19 {20 dfs(nex[x]);21 low[x]=min(low[x],low[ nex[x] ]);22 }23 else24 {25 if(vis[ nex[x] ]) low[x]=min(low[x],low[ nex[x] ]);26 }27 if(low[x]==id[x])28 {29 color[x]=++bp;30 A[bp]++;31 vis[x]=0;32 while (sta[Top]!=x)33 {34 color[ sta[Top] ]=bp;35 vis[ sta[Top] ]=0;;36 A[bp]++;37 Top--;38 }39 Top--;40 }41 }42 43 int find_out(int x)44 {45 if(touc[x]) return dp[x];46 if(Nex[x]==0) 47 {48 touc[x]=true;49 return dp[x];50 }51 dp[x]+=find_out(Nex[x]);52 touc[x]=true;53 return dp[x];54 }55 56 int main()57 {58 scanf("%d",&n);59 for (R i=1;i<=n;++i)60 scanf("%d",&nex[i]);61 for (R i=1;i<=n;++i)62 if(!id[i]) dfs(i);63 for (R i=1;i<=n;++i)64 {65 if(color[i]!=color[ nex[i] ])66 Nex[ color[i] ]=color[ nex[i] ];67 dp[ color[i] ]=A[ color[i] ];68 }69 for (R i=1;i<=n;++i)70 printf("%d\n",find_out(color[i]));71 return 0;72 }
最大半联通子图:
题意概述:图中极大半联通子图计数.半联通子图:对于每个无序点对$(u,v)$,满足其中一个点可以到达另一个点.
不难看出强连通分量里的点都是满足条件的,而且一条缩点后的链都是满足条件的,也就是最长链计数.注意重连边时可能会出现重边,排序,去重即可.
1 // luogu-judger-enable-o2 2 # include3 # include 4 # include 5 # include 6 # include 7 # include 8 # include 9 # include 10 # define R register int 11 12 using namespace std; 13 14 const int maxn=100005; 15 const int maxm=1000006; 16 int k,a,b,n,m,x,h,h2,firs[maxn],firs2[maxn],cnt; 17 int r[maxn],id[maxn],low[maxn],color[maxn],siz[maxn],sta[maxn],bp,Top,vis[maxn]; 18 int dp[maxn],f[maxn],ans1,ans2; 19 queue q; 20 bitset t; 21 struct edge 22 { 23 int too,nex; 24 }g[maxm],g2[maxm]; 25 26 void dfs (int x) 27 { 28 low[x]=id[x]=++cnt; 29 vis[x]=true; 30 sta[++Top]=x; 31 int j; 32 for (R i=firs[x];i;i=g[i].nex) 33 { 34 j=g[i].too; 35 if(!id[j]) 36 dfs(j),low[x]=min(low[x],low[j]); 37 else 38 if(vis[j]) low[x]=min(low[x],low[j]); 39 } 40 if(low[x]==id[x]) 41 { 42 color[x]=++bp; 43 siz[bp]++; 44 vis[x]=0; 45 while (sta[Top]!=x) 46 { 47 color[ sta[Top] ]=bp; 48 vis[ sta[Top] ]=0; 49 siz[bp]++; 50 Top--; 51 } 52 Top--; 53 } 54 } 55 56 void add1 (int x,int y) 57 { 58 g[++h].too=y; 59 g[h].nex=firs[x]; 60 firs[x]=h; 61 } 62 63 void add2 (int x,int y) 64 { 65 g2[++h2].too=y; 66 g2[h2].nex=firs2[x]; 67 firs2[x]=h2; 68 } 69 70 inline char gc() 71 { 72 static char now[1<<22],*S,*T; 73 if (T==S) 74 { 75 T=(S=now)+fread(now,1,1<<22,stdin); 76 if (T==S) return EOF; 77 } 78 return *S++; 79 } 80 inline int read() 81 { 82 R x=0,f=1; 83 register char ch=gc(); 84 while(!isdigit(ch)) 85 { 86 if (ch=='-') f=-1; 87 ch=gc(); 88 } 89 while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=gc(); 90 return x*f; 91 } 92 93 int main() 94 { 95 scanf("%d%d%d",&n,&m,&x); 96 for (R i=1;i<=m;++i) 97 { 98 a=read(),b=read(); 99 add1(a,b);100 }101 for (R i=1;i<=n;++i)102 if(!id[i]) dfs(i);103 for (R i=1;i<=n;++i)104 for (R j=firs[i];j;j=g[j].nex)105 {106 k=g[j].too;107 if(color[i]==color[k]) continue;108 add2(color[i],color[k]);109 }110 for (R i=1;i<=bp;++i)111 {112 for (R j=firs2[i];j;j=g2[j].nex)113 {114 k=g2[j].too;115 if(t[k]) g2[j].too=0;116 else r[k]++;117 t[k]=true;118 }119 for (R j=firs2[i];j;j=g2[j].nex)120 {121 k=g2[j].too;122 t[k]=false;123 }124 }125 for (R i=1;i<=bp;++i)126 if(!r[i]) q.push(i),dp[i]=siz[i],f[i]=1;127 int beg,j;128 while (q.size())129 {130 beg=q.front();131 q.pop();132 for (R i=firs2[beg];i;i=g2[i].nex)133 {134 j=g2[i].too;135 if(dp[beg]+siz[j]>dp[j]) dp[j]=dp[beg]+siz[j],f[j]=f[beg];136 else if(dp[beg]+siz[j]==dp[j]) f[j]=(f[j]+f[beg])%x;137 r[j]--;138 if(!r[j]) q.push(j);139 }140 }141 for (R i=1;i<=bp;++i)142 {143 if(dp[i]>ans1)144 ans1=dp[i],ans2=f[i];145 else if(dp[i]==ans1)146 ans2=(ans2+f[i])%x;147 }148 printf("%d\n%d",ans1,ans2);149 return 0;150 }
抢掠计划:
题意概述:缩点+dp.
这道题的关键点:源点是给定的；
注意最开始入队的时候和平常没有什么区别，但是要单独维护一个$f$数组表示能否从源点到达这个地方.
1 # include2 # include 3 # include 4 # define R register int 5 6 using namespace std; 7 8 const int maxn=500005; 9 int TO[maxn],n,m,x,y,s,p,cnt,bp,vis[maxn],v[maxn],id[maxn],low[maxn],col[maxn],A[maxn],ans,sta[maxn],r[maxn],dp[maxn],Top,goa[maxn]; 10 struct edge 11 { 12 int too,nex; 13 }; 14 int q[maxn],h,t; 15 namespace bef 16 { 17 int h=0,firs[maxn]={ 0}; 18 edge g[maxn]; 19 void add (int x,int y) 20 { 21 g[++h].nex=firs[x]; 22 firs[x]=h; 23 g[h].too=y; 24 } 25 } 26 namespace aft 27 { 28 int h=0, firs[maxn]={ 0}; 29 edge g[maxn]; 30 void add(int x, int y) 31 { 32 g[++h].nex=firs[x]; 33 firs[x]=h; 34 g[h].too=y; 35 } 36 } 37 38 void Tarjan (int x) 39 { 40 id[x]=low[x]=++cnt; 41 sta[++Top]=x; 42 vis[x]=1; 43 int j; 44 for (R i=bef::firs[x];i;i=bef::g[i].nex) 45 { 46 j=bef::g[i].too; 47 if(!id[j]) 48 { 49 Tarjan(j); 50 low[x]=min(low[x],low[j]); 51 } 52 else 53 { 54 if(vis[j]) low[x]=min(low[x],id[j]); 55 } 56 } 57 if(low[x]==id[x]) 58 { 59 col[x]=++bp; 60 A[bp]+=v[x]; 61 vis[x]=0; 62 while (sta[Top]!=x) 63 { 64 A[bp]+=v[ sta[Top] ]; 65 col[ sta[Top] ]=bp; 66 vis[ sta[Top] ]=0; 67 Top--; 68 } 69 Top--; 70 } 71 } 72 73 int main() 74 { 75 scanf("%d%d",&n,&m); 76 for (R i=1;i<=m;++i) 77 { 78 scanf("%d%d",&x,&y); 79 bef::add(x,y); 80 } 81 for (R i=1;i<=n;++i) 82 scanf("%d",&v[i]); 83 scanf("%d%d",&s,&p); 84 for (R i=1;i<=p;++i) 85 scanf("%d",&goa[i]); 86 for (R i=1;i<=n;++i) 87 if(!id[i]) Tarjan(i); 88 int beg,k; 89 for (R i=1;i<=n;++i) 90 for (R j=bef::firs[i];j;j=bef::g[j].nex) 91 { 92 k=bef::g[j].too; 93 if(col[i]!=col[k]) aft::add(col[i],col[k]),r[ col[k] ]++; 94 95 } 96 for (R i=1;i<=bp;++i) 97 if(!r[i]) q[++t]=i; 98 h=1; 99 dp[ col[s] ]=A[ col[s] ];100 TO[ col[s] ]=1;101 while (h<=t)102 {103 beg=q[h];104 h++;105 for (R i=aft::firs[beg];i;i=aft::g[i].nex)106 {107 k=aft::g[i].too;108 r[k]--;109 if(TO[beg])110 {111 TO[k]=true;112 dp[k]=max(dp[k],dp[beg]+A[k]);113 }114 if(!r[k]) q[++t]=k;115 }116 }117 for (R i=1;i<=p;++i)118 ans=max(ans,dp[ col[ goa[i] ] ]);119 printf("%d",ans);120 return 0;121 }
间谍网络:
首先缩点,然后找到入度为$0$的点收买即可.对于一个强联通分量里的点,如果要收买只需要收买那个最便宜的即可.
1 # include2 # include 3 # include 4 # include 5 # define R register int 6 7 using namespace std; 8 9 const int maxn=3003; 10 const int maxm=8003; 11 int n,p,x,y,v,m,h,cnt,beg,ans; 12 int a[maxn],id[maxn],low[maxn],sta[maxn],Top,vis[maxn],col[maxn],A[maxn],bp,r[maxn],tr[maxn]; 13 struct edge 14 { 15 int too,nex; 16 }; 17 queue q; 18 19 namespace shzr 20 { 21 int firs[maxn],h; 22 edge g[maxm]; 23 void add (int x,int y) 24 { 25 g[++h].too=y; 26 g[h].nex=firs[x]; 27 firs[x]=h; 28 } 29 } 30 namespace asu 31 { 32 int firs[maxn],h; 33 edge g[maxm]; 34 void add (int x,int y) 35 { 36 g[++h].too=y; 37 g[h].nex=firs[x]; 38 firs[x]=h; 39 } 40 } 41 42 void Tarjan (int x) 43 { 44 id[x]=low[x]=++cnt; 45 sta[++Top]=x; 46 vis[x]=1; 47 int j; 48 for (R i=shzr::firs[x];i;i=shzr::g[i].nex) 49 { 50 j=shzr::g[i].too; 51 if(!id[j]) 52 { 53 Tarjan(j); 54 low[x]=min(low[x],low[j]); 55 } 56 else 57 { 58 if(vis[j]) low[x]=min(low[x],id[j]); 59 } 60 } 61 if(low[x]==id[x]) 62 { 63 col[x]=++bp; 64 A[bp]=a[x]; 65 vis[x]=false; 66 while(sta[Top]!=x) 67 { 68 col[ sta[Top] ]=bp; 69 if(A[bp]==-1) A[bp]=a[ sta[Top] ]; 70 else if(a[ sta[Top] ]!=-1) A[bp]=min(A[bp],a[ sta[Top] ]); 71 vis[ sta[Top] ]=false; 72 Top--; 73 } 74 Top--; 75 } 76 } 77 78 int main() 79 { 80 scanf("%d%d",&n,&p); 81 memset(a,-1,sizeof(a)); 82 for (R i=1;i<=p;++i) 83 { 84 scanf("%d%d",&x,&v); 85 a[x]=v; 86 } 87 scanf("%d",&m); 88 for (R i=1;i<=m;++i) 89 { 90 scanf("%d%d",&x,&y); 91 shzr::add(x,y); 92 } 93 for (R i=1;i<=n;++i) 94 if(!id[i]) Tarjan(i); 95 int k; 96 for (R i=1;i<=n;++i) 97 for (R j=shzr::firs[i];j;j=shzr::g[j].nex) 98 { 99 k=shzr::g[j].too;100 if(col[i]==col[k]) continue;101 asu::add(col[i],col[k]);102 r[ col[k] ]++;103 }104 for (R i=1;i<=bp;++i)105 if(!r[i]) q.push(i);106 while(q.size())107 {108 beg=q.front();109 q.pop();110 if(tr[beg]==false&&A[beg]!=-1) ans+=A[beg],tr[beg]=true;111 for (R i=asu::firs[beg];i;i=asu::g[i].nex)112 {113 k=asu::g[i].too;114 tr[k]|=tr[beg];115 r[k]--;116 if(!r[k]) q.push(k);117 }118 }119 for (R i=1;i<=n;++i)120 if(tr[ col[i] ]==false)121 {122 printf("NO\n%d",i);123 return 0;124 }125 printf("YES\n%d",ans);126 return 0;127 }
---shzr