Tarjan-縮點

　　$Tarjan$縮點

　　Tarjan的第二個應用就是求縮點啦。縮點雖然比割點麻煩一點，但是用處也比割點要大不少。

　　本來要學另外兩個縮點算法的,但是似乎沒什么用...$MST$里確實有只能有$prim$或者只能用$kruscal$的題目，但是這三種縮點...在網上沒有找到介紹它們之間作用差異的文章,可能真的沒有什么區別吧.

　　縮點是對于有向圖來說的。首先什么是強連通分量：里面的點兩兩之間互相可達。如果一道題中互相可達的點有某種神秘的聯系(一個強連通分量等價于一個點的作用)時，就可以進行縮點。那么縮點有什么好處呢，顯而易見的是可以快，把一些等價的點的操作一起做了，還有一個就是縮完點之后的圖必然是一個$Dag$，可以在上面跑一些拓撲排序啊，$dp$啊之類的東西。　　

　　首先先看一個模板吧：

　　縮點：https://www.luogu.org/problemnew/show/P3387

　　題意概述：縮點后跑dp，求點權最大的路徑，每個點的點權只算一次；

  1 # include <cstdio>
  2 # include <iostream>
  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<<ans;
100     return 0;
101 }

縮點

　　牛的舞會：https://www.luogu.org/problemnew/show/P2863

　? 題意概述：找到大小大于1的強連通分量個數。

　　板子題*2，再開一個數組記錄每個連通分量的大小就行啦。

 1 # include <cstdio>
 2 # include <iostream>
 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 edge
11 {
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         else
37         {
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<<Ans;
71     return 0;
72 }

牛的舞會

　　受歡迎的牛：https://www.luogu.org/problemnew/show/P2341

　　題意概述：求圖中某種點的個數（其余所有的點都可以通過某些路徑到達它這里的點）。

　　因為路徑可以繞來繞去，所以一個強連通分量里的點要么全是這種點，要么全都不是。如果一個強連通分量有出邊，它必然不是一個受歡迎的強連通分量（它連出去的邊一定沒有連回來，否則就合成同一個連通分量了）。也就是說，找到唯一一個出度為$0$的強連通分量，它的大小就是答案。如果有不止一個這樣的分量，說明圖不連通，答案為$0$。

 1 # include <cstdio>
 2 # include <iostream>
 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 edge
12 {
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         else
38         {
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             else
82             {
83                 printf("0");
84                 return 0;
85             }
86         }
87     }
88     printf("%d",ans);
89     return 0;
90 }

受歡迎的牛

　　在農場萬圣節：https://www.luogu.org/problemnew/show/P2921

?? 題意概述：給定一張有向圖，求從每個點出發路過的點的個數。（每個點的后繼唯一，不能走重復點）。

　看起來縮點非常可行，且走進一個分量就出不來了，所以縮點后進行記憶化搜索就可以啦。這道題有一個簡化的地方，每個點只有單一的后繼，所以不用前向星，只用一個$nex$數組也是完全可以的。

 1 # include <cstdio>
 2 # include <iostream>
 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     else
24     {
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 }

在農場萬圣節

　　最大半聯通子圖:https://www.luogu.org/problemnew/show/P2272

　　題意概述:圖中極大半聯通子圖計數.半聯通子圖:對于每個無序點對$(u,v)$,滿足其中一個點可以到達另一個點.

　　不難看出強連通分量里的點都是滿足條件的,而且一條縮點后的鏈都是滿足條件的,也就是最長鏈計數.注意重連邊時可能會出現重邊,排序,去重即可.

  1 // luogu-judger-enable-o2
  2 # include <cstdio>
  3 # include <iostream>
  4 # include <cstring>
  5 # include <cmath>
  6 # include <algorithm>
  7 # include <string>
  8 # include <bitset>
  9 # include <queue>
 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 <int> q;
 20 bitset <maxn> 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 }

最大半聯通子圖

　　搶掠計劃:https://www.luogu.org/problemnew/show/P3627

　　題意概述:縮點+dp.

　　這道題的關鍵點:源點是給定的；

　　注意最開始入隊的時候和平常沒有什么區別，但是要單獨維護一個$f$數組表示能否從源點到達這個地方.

  1 # include <cstdio>
  2 # include <iostream>
  3 # include <queue>
  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 }

搶掠計劃

　　間諜網絡:https://loj.ac/problem/10095

　　首先縮點,然后找到入度為$0$的點收買即可.對于一個強聯通分量里的點,如果要收買只需要收買那個最便宜的即可.

  1 # include <cstdio>
  2 # include <iostream>
  3 # include <cstring>
  4 # include <queue>
  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 <int> 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 }