Tarjan进阶

╰半夏微凉° 2021-11-16 10:14 293阅读 0赞

# BLO #

关键字：tarjan 树上dp

原图有环，然可利用tarjan深度优先搜索树，假设去掉的点是u，考虑三个方向的转移

1.  本身：2\*(n-1)，与除本身外任何点构成有序点对
2.  儿子与儿子：不能够计算所有的儿子。举例：u节点有一字节点v与u的祖先节点成强连通分量，即去掉u后 v和u的祖先依然连通，不能计算v和u祖先。所以统计以下不满足以上性质的sum
3.  儿子与父亲：若u是割点，则v与fa（及2中特殊的vi）不连通，计算贡献sum\*(n-sum-1)\*2

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<queue>
     3 #include<cstring>
     4 #include<algorithm>
     5 #define MAXN 100005
     6 #define MAXM 500005
     7 #define ll long long
     8 #define reg register
     9 #define F(i,a,b) for(i=a;i<=b;++i)
    10 using namespace std;
    11 inline int read();
    12 struct R{
    13     int u,v,next;
    14 }r[MAXM<<1];
    15 int n,m,top,now;
    16 int fir[MAXN],o=1;
    17 int dfn[MAXN],low[MAXN],save[MAXN],stack[MAXN],siz[MAXN],cut[MAXN],d[MAXN];
    18 vector<int> to[MAXN];
    19 ll ans[MAXN];
    20 void add(int u,int v)
    21 {
    22     r[o].u=u;
    23     r[o].v=v;
    24     r[o].next=fir[u];
    25     fir[u]=o++;
    26 }
    27 void Tarjan(int u,int fa)
    28 {
    29     dfn[u]=low[u]=++now;
    30     int flag=0,sum=0;
    31     reg int i,v;
    32     siz[u]=1;
    33     for(i=fir[u];i;i=r[i].next)
    34     {
    35         v=r[i].v;
    36         if(!dfn[v])
    37         {
    38             Tarjan(v,u);
    39             siz[u]+=siz[v];
    40             low[u]=min(low[u],low[v]);
    41             if(low[v]>=dfn[u])
    42             {
    43                 ++flag;
    44                 to[u].push_back(v);
    45                 sum+=siz[v];
    46                 if(u!=1||flag>1) cut[u]=1;
    47             }
    48         }
    49         else low[u]=min(low[u],dfn[v]);
    50     }
    51     if(cut[u])
    52     {
    53         for(i=0;i<to[u].size();++i)
    54         {
    55             v=to[u][i];
    56             ans[u]+=1ll*(sum-siz[v])*siz[v];
    57         }
    58         ans[u]+=1ll*sum*(n-sum-1)*2;
    59     }
    60     ans[u]+=1ll*(n-1)*2;
    61 }
    62 int main()
    63 {
    64     n=read(); m=read();
    65     reg int i,a,b;
    66     F(i,1,m)
    67     {
    68         a=read(); b=read();
    69         add(a,b); add(b,a);
    70     }
    71     Tarjan(1,0);
    72     F(i,1,n) printf("%lld\n",ans[i]);
    73     return 0;
    74 }
    75 inline int read()
    76 {
    77     reg int x=0;
    78     reg char c;
    79     c=getchar();
    80     while(c<'0'||c>'9') c=getchar();
    81     while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    82     return x;
    83 }

# \[BeiJing2013\]压力 #

关键字：tarjan 双连通分量 缩点 lca 树上差分

求必须通过的节点数

*  显然 割点必经过
 *  假设有一个点双连通分量，则去掉其中任何一点依然连通，即任何一点都不是"必须经过"

所以当点双连通分量上的点作为在路径上且不为路径端点的点无贡献，但需保证图的连通性所以不能把分量撇掉，我们完全可以把它（们）看成一个点，然后缩点建树

类似雨天的尾巴，不过本题只有一种“物品”，直接裸树上差分，统计出割点的贡献加到ans里

对于起点和终点规定一定经过，直接++即可

缩点：不同于e-dcc，删掉割点后形成的各个连通块不是所求点双。每个点双内都有该割点，所以tarjan退栈到v后要把u加到dcc中。

标记：

*  点双连通分量的“缩点”会“增点”，假设有n个dcc p个割点，由于对每个割点建新点，则缩点后有n+p个点。考虑最坏情况一条链，显然要x2，提示mle调了好久，总是有数组没x2
 *  lca的d深度数组要给根赋值1，不然以下横成立直接跳

for(reg int i=h;i>=0;--i) if(d[f[y][i]]>=d[x]) y=f[y][i];

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
      2 #include<queue>
      3 #include<cmath>
      4 #include<bitset>
      5 #include<cstring>
      6 #include<algorithm>
      7 #define MAXN 100005
      8 #define MAXM 200005
      9 #define ll long long
     10 #define reg register
     11 #define F(i,a,b) for((i)=(a);(i)<=(b);++(i))
     12 using namespace std;
     13 inline int read();
     14 struct R{
     15     int u,v,next;
     16 }r[MAXM<<1],sr[MAXM*4];
     17 int n,m,ask,fir[MAXN],sec[MAXN<<1],o=1;
     18 int dfn[MAXN],low[MAXN],bl[MAXN],stack[MAXN],id[MAXN],now,cnt,top,root;
     19 int d[MAXN<<1],f[MAXN<<1][19],h;
     20 int w[MAXN<<1],ans[MAXN<<1],pt[MAXN];
     21 bool cut[MAXN];
     22 vector<int> dcc[MAXN];
     23 inline void add(int u,int v,int fir[],R r[])
     24 {
     25     r[o].u=u;
     26     r[o].v=v;
     27     r[o].next=fir[u];
     28     fir[u]=o++;
     29 }
     30 void Tarjan(int u)
     31 {
     32     int i,v,flag=0;
     33     dfn[u]=low[u]=++now;
     34     stack[++top]=u;
     35     for(i=fir[u];i;i=r[i].next)
     36     {
     37         v=r[i].v;
     38         if(!dfn[v])
     39         {
     40             Tarjan(v);
     41             low[u]=min(low[u],low[v]);
     42             if(dfn[u]<=low[v])                //割点判断
     43             {
     44                 ++flag;
     45                 if(u!=root||flag>1) cut[u]=1;        //若是根则有两个“回溯祖先”才是割点
     46                 ++cnt;
     47                 int y;
     48                 do{
     49                     y=stack[top--];
     50                     dcc[cnt].push_back(y);
     51                 }while(y!=v);
     52                 dcc[cnt].push_back(u);                //割点要算到每个dcc中
     53             }
     54         }
     55         else low[u]=min(low[u],dfn[v]);
     56     }
     57 }
     58 void dfs(int u)
     59 {
     60     int v;
     61     for(reg int i=sec[u];i;i=sr[i].next)
     62     {
     63         v=sr[i].v;
     64         if(v==f[u][0]) continue;
     65         d[v]=d[u]+1;
     66         f[v][0]=u;
     67         for(reg int j=1;j<=h;++j) f[v][j]=f[f[v][j-1]][j-1];
     68         dfs(v);
     69     }
     70 }
     71 int lca(int x,int y)
     72 {
     73     if(d[x]>d[y]) x^=y^=x^=y;
     74     for(reg int i=h;i>=0;--i) if(d[f[y][i]]>=d[x]) y=f[y][i];
     75     if(x==y) return x;
     76     for(reg int i=h;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
     77     return f[x][0];
     78 }
     79 void dfs2(int u)
     80 {
     81     int v;
     82     for(reg int i=sec[u];i;i=sr[i].next)
     83     {
     84         v=sr[i].v;
     85         if(v==f[u][0]) continue;
     86         dfs2(v);
     87         w[u]+=w[v];
     88     }
     89     ans[u]=w[u];
     90 }
     91 int main()
     92 {
     93     n=read(); m=read(); ask=read();
     94     int a,b,i;
     95     h=(int)log2(n)+1;
     96     F(i,1,m)
     97     {
     98         a=read(); b=read();
     99         add(a,b,fir,r); add(b,a,fir,r);
    100     }
    101     F(i,1,n) if(!dfn[i]){root=i;Tarjan(i);}
    102     int num=cnt,v;
    103     F(i,1,n) if(cut[i]) id[i]=++num;
    104     F(i,1,cnt)
    105     {
    106         for(reg int j=0;j<dcc[i].size();++j)
    107         {
    108             v=dcc[i][j];
    109             if(cut[v])
    110             {
    111                 add(i,id[v],sec,sr);
    112                 add(id[v],i,sec,sr);
    113                 bl[v]=id[v];
    114             }
    115             else bl[v]=i;
    116         }
    117     }
    118     d[1]=1;            //!!!
    119     dfs(1);
    120     int lc;
    121     F(i,1,ask)
    122     {
    123         a=read(); b=read();
    124         lc=lca(bl[a],bl[b]);
    125         ++w[bl[a]];
    126         ++w[bl[b]];
    127         ++pt[a];
    128         ++pt[b];
    129         --w[lc];
    130         --w[f[lc][0]];
    131     }
    132     dfs2(1);
    133     F(i,1,n) if(cut[i]) pt[i]=ans[id[i]];
    134     F(i,1,n) printf("%d\n",pt[i]);
    135     return 0;
    136 }
    137 inline int read()
    138 {
    139     int reg x=0;
    140     reg char c;
    141     c=getchar();
    142     while(c<'0'||c>'9') c=getchar();
    143     while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    144     return x;
    145 }

# Redundant Paths 分离的路径 #

关键字：tarjan 边双板子

边双都满足题意，思想同上，但e-dcc的缩点与v-dcc不同。

我们只要找出所有的桥，然后除去桥外形成的连通块缩点。

对于缩点后的树，答案为(叶子节点数+1)/2，感性理解下，每次把叶子节点连接，能形成最优的双连通分量（假设我们连接非叶子节点，则连接节点以下不能构成双连通），又因为是无向边/2。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<queue>
     3 #include<bitset>
     4 #include<cstring>
     5 #include<algorithm>
     6 #define MAXN 5005
     7 #define MAXM 10005
     8 #define ll long long
     9 #define reg register
    10 #define F(i,a,b) for(i=a;i<=b;++i)
    11 using namespace std;
    12 inline int read();
    13 struct R{
    14     int u,v,next;
    15 }r[MAXM<<1];
    16 int n,m,fir[MAXN],o=1;
    17 int dfn[MAXN],low[MAXN],bl[MAXN],du[MAXN],now,dcc;
    18 bool isbg[MAXM];
    19 inline void add(int u,int v,int fir[],R r[])
    20 {
    21     r[++o].u=u;
    22     r[o].v=v;
    23     r[o].next=fir[u];
    24     fir[u]=o;
    25 }
    26 void Tarjan(int u,int ie)
    27 {
    28     dfn[u]=low[u]=++now;
    29     reg int i,v;
    30     for(i=fir[u];i;i=r[i].next)
    31     {
    32         v=r[i].v;
    33         if(!dfn[v])
    34         {
    35             Tarjan(v,i);
    36             low[u]=min(low[u],low[v]);
    37             if(low[v]>dfn[u]) isbg[i]=isbg[i^1]=1;
    38         }
    39         else if(i!=(ie^1)) low[u]=min(low[u],dfn[v]);
    40     }
    41 }
    42 void dfs(int u)
    43 {
    44     reg int i,v;
    45     bl[u]=dcc;
    46     for(i=fir[u];i;i=r[i].next)
    47     {
    48         v=r[i].v;
    49         if(bl[v]||isbg[i]) continue;
    50         dfs(v);
    51     }
    52 }
    53 void getdcc()
    54 {
    55     reg int i;
    56     F(i,1,n)
    57     {
    58         if(bl[i]) continue;
    59         ++dcc;
    60         dfs(i);
    61     }
    62 }
    63 int main()
    64 {
    65     n=read(); m=read();
    66     reg int i,a,b;
    67     F(i,1,m)
    68     {
    69         a=read(); b=read();
    70         add(a,b,fir,r); add(b,a,fir,r);
    71     }
    72     F(i,1,n) if(!dfn[i]) Tarjan(i,0);
    73     getdcc();
    74 //    for(i=2;i<=(m<<1);i+=2) if(isbg[i]) add(bl[r[i].u],bl[r[i].v],sec,sr),add(bl[r[i].v],bl[r[i].u],sec,sr);   //有重边一定是边双
    75     for(i=2;i<=(m<<1);i+=2) if(isbg[i]) ++du[bl[r[i].u]],++du[bl[r[i].v]];
    76     reg int cnt=0;
    77     F(i,1,dcc) if(du[i]==1) ++cnt;
    78     printf("%d",(cnt+1)/2);
    79     return 0;
    80 }
    81 inline int read()
    82 {
    83     reg int x=0;
    84     reg char c;
    85     c=getchar();
    86     while(c<'0'||c>'9') c=getchar();
    87     while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    88     return x;
    89 }

# Knights of the Round Table #

关键字：语文素养考察题 tarjan点双 补图 奇环（二分图黑白染色法）

一开始没有理解题

*  我求的是有可能被驱逐的（n-必须）
 *  错误地认为只有一桌，每个人参加与否是固定的。又因为求的是“必须”，所以我就开始码求最大奇环

所以只有在正确地理解了题意后才应开始码，不然爆零两行泪T T

然后对于点双我们有一下推论：

*  如果点双内部分点构成奇环，则整个点双可以构成奇环。假设部分点构成的奇环G上有两点u v，G外有一点k，知u v间的距离s1 s2一奇一偶，k与u v的距离之和s3（确定）可奇可偶，所以s1+s3或s2+s3其中一定一奇一偶，则一定构成奇环。

然后对于每个dcc分别跑dfs染色即可，只要存在一个奇环，则所有u属于dcc都可能参加。

注意：dfs的边界判断，不能走到其他的dcc

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
      2 #include<vector>
      3 #include<cstring>
      4 #include<algorithm>
      5 #define MAXN 1005
      6 #define MAXM 1000005
      7 #define reg register
      8 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
      9 using namespace std;
     10 inline int read();
     11 int fir[MAXN],o=1;
     12 int dfn[MAXN],low[MAXN],stack[MAXN],col[MAXN],id[MAXN],cnt,top,now;
     13 bool hate[MAXN][MAXN],pt[MAXN];
     14 vector<int> dcc[MAXN];
     15 struct R{
     16     int u,v,next;
     17 }r[MAXM<<1];
     18 void add(int u,int v)
     19 {
     20     r[++o].u=u;
     21     r[o].v=v;
     22     r[o].next=fir[u];
     23     fir[u]=o;
     24 }
     25 void Tarjan(int u)
     26 {
     27     int v;
     28     dfn[u]=low[u]=++now;
     29     stack[++top]=u;
     30     for(reg int i=fir[u];i;i=r[i].next)
     31     {
     32         v=r[i].v;
     33         if(!dfn[v])
     34         {
     35             Tarjan(v);
     36             low[u]=min(low[u],low[v]);
     37             if(dfn[u]<=low[v])
     38             {
     39                 int y;
     40                 ++cnt;
     41                 do{
     42                     y=stack[top--];
     43                     dcc[cnt].push_back(y);
     44                 }while(y!=v);
     45                 dcc[cnt].push_back(u);
     46             }
     47         }
     48         else low[u]=min(low[u],dfn[v]);
     49     }
     50 }
     51 bool dfs(int u,int co,int signn)
     52 {
     53     int v;
     54     col[u]=co;
     55     for(reg int i=fir[u];i;i=r[i].next)
     56     {
     57         v=r[i].v;
     58         if(id[v]!=signn) continue;
     59         if(!col[v]){
         if(dfs(v,3-co,signn)) return 1;}
     60         else if(col[v]==co) return 1;
     61     }
     62     return 0;
     63 }
     64 int main()
     65 {
     66     int n,m;
     67 //    freopen("data.in","r",stdin);
     68 //    freopen("data.out","w",stdout);
     69     while(scanf("%d %d",&n,&m)==2&&n&&m)
     70     {
     71         int a,b;
     72         F(i,1,n) dcc[i].clear();
     73         memset(hate,0,sizeof(hate));
     74         memset(dfn,0,sizeof(dfn));
     75         memset(low,0,sizeof(low));
     76         memset(fir,0,sizeof(fir));
     77         memset(r,0,sizeof(r));
     78         memset(id,0,sizeof(id));
     79         memset(pt,0,sizeof(pt));
     80         o=1;
     81         cnt=0;
     82         now=0;
     83         top=0;
     84         F(i,1,n) hate[i][i]=1;
     85         F(i,1,m)
     86         {
     87             a=read(); b=read();
     88             hate[a][b]=hate[b][a]=1;
     89         }
     90         F(i,1,n)
     91             F(j,1,n)
     92                 if(!hate[i][j])
     93                     add(i,j);
     94         F(i,1,n) if(!dfn[i]) Tarjan(i);
     95         int v;
     96         F(i,1,cnt)
     97         {
     98             for(reg int j=0;j<dcc[i].size();++j)
     99             {
    100                 v=dcc[i][j];
    101                 col[v]=0;
    102                 id[v]=i;
    103             }
    104             if(dfs(dcc[i][0],1,i))
    105                 for(reg int j=0;j<dcc[i].size();++j)
    106                     pt[dcc[i][j]]=1;
    107         }
    108         reg int ans=0;
    109         F(i,1,n) if(!pt[i]) ++ans;
    110         printf("%d\n",ans);
    111     }
    112     return 0;
    113 }
    114 inline int read()
    115 {
    116     int x=0;
    117     char c=getchar();
    118     while(c<'0'||c>'9') c=getchar();
    119     while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    120     return x;
    121 }

转载于:https://www.cnblogs.com/hzoi-yzh/p/11182219.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/b57f322e057c4641bdedfe79016264fa.png