Skip to content

缩点

主要作用：将有向有环图变成有向无环图（DAG）

整体思路就是dfs，再搜索树中判断环。

有两种指向已经搜索过的点的边，一种是返祖边，即指向自己的祖先节点； 一种是横叉边，即指向自己的非祖先节点。可以证明只有返祖边会产生环。

所以用栈维护当前的搜索链，开两个数组dfn和low维护。只要找到返祖便就退栈到祖先，并将所有点作为一个强连通分量。否则就无视，在回溯是将单个点作为强连通分量。

模板

void tarjan(int u){
    dfn[u]=low[u]=++tot;//low[u]值默认为dfn[u],后面再更新
    stk[++top]=u;//进栈打标记
    vis[u]=1;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);//这一步是为了更新那些再环中的点，如上图的6，7
        }else{
            if(vis[v])low[u]=min(low[u],dfn[v]);//返祖边，找到了环，那就将low[u]更新为当前根节点。

        //横叉边如5->4直接忽略
        }
    }
  //注意只有自己是根才退栈，否则要保留栈中信息。

    if(dfn[u]==low[u]){//如果自己只能回溯到自己，说明自己是强连通分量中的根节点，就退栈到自己，将所有点所称一个点。
        ++nod;
        while(1){
            ans[stk[top]]=nod;
            vis[stk[top]]=0;//去除标记
            if(stk[top--]==u)break;
        }
    }
}
int main(){
    memset(dfn,0,sizeof dfn);
   memset(low,0,sizeof low);
   memset(vis,0,sizeof vis);
   for(int i=1;i<=n;++i){
        if(!dfn[i])tarjan(i);
   }

}

P3387 & P3627

两道题差不多，一个是先缩点，再根据拓扑排序的顺序取dp，这样保证无后效性，最后输出所有点中贡献最大的值；

一个是缩完点后，从新的起点取用SPFA求最长路，最后再酒吧中招最长的就行。

~~太简单不放代码了~~

P1262

将所有的环缩成一个点，并且得到新的点的代价就是环内所有点的最小价钱。

那么必须贿赂的就是入度为零的点，如果无法贿赂就无解。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3010,M=8010,P=20000;
int n,m,p,cnt,top,tot,nod;
int a[N],w[N],head[N],dfn[N],low[N],vis[N],stk[N],ans[N],ind[N];
struct query{
    int u,v;
}q[M];
struct edge{
    int v,nxt;
}e[M<<1];
void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void tarjan(int u){
    dfn[u]=low[u]=++tot;
    stk[++top]=u;
    vis[u]=1;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else{
            if(vis[v])low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ++nod;
        while(1){
            ans[stk[top]]=nod;
            vis[stk[top]]=0;
            if(stk[top--]==u)break;
        }
    }
}
int main(){
    memset(head,-1,sizeof head);
    cnt=-1;
    memset(w,0x3f,sizeof w);
    memset(a,0x3f,sizeof a);
    scanf("%d%d",&n,&p);
    for(int i=1,tmp,pos;i<=p;++i)scanf("%d%d",&pos,&tmp),a[pos]=tmp;
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&q[i].u,&q[i].v);
        add(q[i].u,q[i].v);
    }
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);

    for(int i=1;i<=n;++i){
        w[ans[i]]=min(w[ans[i]],a[i]);
    }

    for(int i=1;i<=m;++i){
        int uu=ans[q[i].u],vv=ans[q[i].v];
        if(uu==vv)continue;
        ind[vv]++;
    }
    memset(vis,0,sizeof vis);
    int res=0;
    bool flag=true;
    for(int i=1;i<=nod;++i){
        if(!ind[i]){
            if(w[i]<=P){
                res+=w[i];  
            }else{
                vis[i]=1;
                flag=false;
            }
        }
    }
    if(flag){
        printf("YES\n%d",res);
    }else{
        int minn=N+N;
        for(int i=1;i<=n;++i){
            if(vis[ans[i]])minn=min(minn,i);
        }
        printf("NO\n%d",minn);
    }
    return 0;
} 
/*
7
6
5 100
1 99
2 98
3 101
4 102
7 200
7
5 1
1 2
2 6
1 4
4 5
2 3 
3 1
*/

tarjan求割点

同样是利用\(low\)和\(dfn\)数组。

对于tarjan的一次搜索，由于不会到\(dfn\)数组不为0的点继续搜索，因此，整个过程形成一颗搜索树。对这个搜索树中，可能为割点有2种情况:

  1. 根节点，且儿子大于等于2
  2. \(dfn[u]\leq low[v]\)的点。

因为\(v\)可能回溯到的最靠前的点都大于\(u\)，说明\(v\)不能通过除了\(u\)以外的点与剩余比\(dfn[u]\)小的点联通，所以\(u\)是割点。

#include<iostream>
#include<cstring>
using namespace std;
const int N=2e4+10,M=1e5+10;
struct edge{
    int v,nxt;
}e[M<<1];
int n,m,u,v,tot,cnt;
int dfn[N],low[N],cut[N],head[N];
void add(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

void tarjan(int u,int p){
    dfn[u]=low[u]=++tot;
    int son=0;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v,p);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u] && u!=p) cut[u]=1; 
            if(u==p) ++son; 
        }else low[u]=min(low[u],dfn[v]);
    }
    if(son>=2 && u==p) cut[u]=1;
}
int main(){
    memset(head,-1,sizeof head);
    cnt=-1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i){
        if(!dfn[i]) tarjan(i,i);
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        if(cut[i]) ++ans;
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;++i){
        if(cut[i]) printf("%d ",i);
    }
    return 0;
}

P3469

由于搜索时一棵树，所以可以维护\(sz\)数组。答案即为\(\sum sz[v]*(n-sz[v])\)，\(sz[v]\)可以在搜索中得到。

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+10,M=5e5+10;
struct edge{
    int v,nxt;
}e[M<<1];
int head[N],dfn[N],low[N],sz[N],ans[N];
int cnt,n,m,u,v,tot;
void add(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
void tarjan(int u){
    dfn[u]=low[u]=++tot;
    int r=n-1;
    sz[u]=1;ans[u]=r;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v),sz[u]+=sz[v],low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) ans[u]+=sz[v]*(n-sz[v]),r-=sz[v];
        }else low[u]=min(low[u],dfn[v]);
    }
    ans[u]+=r*(n-r);
}
signed main(){
    memset(head,-1,sizeof head);
    cnt=-1;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%lld",&u,&v);
        add(u,v),add(v,u);
    }
    tarjan(1);
    for(int i=1;i<=n;++i){
        printf("%lld\n",ans[i]);
    }
    return 0;
}