tarjan学习笔记2 缩点【tarjan】

作者: wjyyy 分类: tarjan,学习笔记 发布时间: 2018-06-06 18:36

点击量:51

   例题是洛谷P3387缩点

 

   顾名思义,缩点就是将等价的几个点转化为一个点,点权可累加。那么我们就要用tarjan来求一下哪些点可以缩在一起。

 

1.dfn和low的含义

   tarjan算法有两个核心数组:dfn和low,同样也需要一个栈,辅助存储强连通分量。dfn是“时间戳”,dfn[i]说明i点在什么时间被遍历的。low[i]是i可回溯到的最早时间戳的点的时间戳(见下面对low值的计算),默认值为dfn[i],举个例子:如果i到j有一条路径,j到i也有一条路径,那么就使\(max(low[i],low[j])=min(low[i],low[j])\) 虽然不符合语法,并将路上的点入栈,打上在栈内的标记in。

 

2.强连通分量的根

   如果一个点i的dfs做完后没有找到能回溯到的点,那么会有dfn[i]==low[i],i就是i所在强连通分量(树)的根节点。因为树根是i,由dfs的栈性质,从s栈顶到i所在位置均没有强连通分量的根节点,所以将这些点出栈,归为同一个强连通分量++cnt。


   上面的做法也可以直接用并查集并在一起,不过访问时可能会比较麻烦。


   在dfs过程中,如果遍历到一个点k,并且k不在栈中,\(dfn[k]>0(\Leftrightarrow k \notin \)这个强连通分量中),则k与这个强连通分量没有关系,因为它被其他分量更新了,而正在处理的强连通分量因为没有被更新,所以两个分量不能在一起(即 不等价)。

 

3.low数组的求法

   如果dfn[i]!=low[i],说明i不是其所属强连通分量的根节点。刚进入dfs函数时,将该点压入栈内(与第二点第二句照应)。如果dfs(x)时找到一个点k在栈内,(有向图中)就成环了,这个环就可以被看作是一个点。赋值low[x]=min(low[x],low[x]);即x点可以回溯\(\Rightarrow \)x点在k点的强连通分量中,也在环上。不过这个过程还没结束,一个强连通分量可能不止一个环,所以我们还需要继续dfs下去。如果一个点指向的点low值更新了,那么它的low就更新成更小的值,防止误判为“根节点”,需要注意的是:如果找到一个可回溯的点,只更新,不能继续dfs,不然会一直循环下去。在过程结束之后,如果没有更新low的值,说明low是根节点,去到第二点中

 

4.其他

    图可能被分为几块,一次dfs不一定能找全所有的强连通分量而导致CE(调用NULL)。所以在dfs时应该枚举开始做的点,一旦dfn==0,就从它开始做。

 

5.针对这个题【洛谷P3387】

   缩点后,原来的图会被缩成更小的图,强连通分量被视作一个点,这个点的权值是分量中所有点的权值之和。接着枚举每条边,如果边的两端跨越了分量,就把它连上(不能再用原来的图),对入度为0的点做dfs,在近似O(N)的复杂度内可以找出正确答案。

 

Code:(P3387标程)

#include<cstdio>
#include<cstring>
int min(int x,int y){return x<y?x:y;}
struct node
{
    int n;
    node *nxt;
    node (int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node(){nxt==NULL;}
};
node head[10200],*tail[10200];
int dfn[10200],low[10200];
int v[10200],cnt=0;
bool in[10020];//是否在栈中
int s[10020],top=0;//栈
int Index=0;//第几个强连通分量
int y_n[10020],y_v[10020];//分别存储第i个点属于哪个强连通分量,以及存储第i个强连通分量的权值
void dfs(int x)
{
    if(!dfn[x])
    {
        dfn[x]=++cnt;
        low[x]=dfn[x];//新时间戳
    }
    s[++top]=x;//入栈并标记
    in[x]=true;
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(dfn[p->n]&&!in[p->n])//不在同一个强连通分量
            continue;
        if(in[p->n])
        {
            low[x]=min(low[p->n],low[x]);//更新可回溯的值
            continue;
        }
        dfs(p->n);
        low[x]=min(low[x],low[p->n]);//如果下一个点可回溯则当前点也可回溯
    }
    if(dfn[x]==low[x])//x是强连通分量的根节点,可以退栈了
    {
        y_n[x]=++Index;
        while(s[top]!=x)
        {
            in[s[top]]=false;
            y_n[s[top]]=Index;
            y_v[Index]+=v[s[top]];
            top--;
        }
        in[s[top]]=false;//出栈时要更改状态
        y_n[s[top]]=Index;//存储s[top]属于哪个强连通分量
        y_v[Index]+=v[s[top]];
        top--;
    }
    return;
}
int n,ans=0,maxx=0;
node Head[10020],*Tail[10020];
void Dfs(int x)//在建的新图中找最长点权和的链
{
    node *p=&Head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        ans+=y_v[p->n];//当前已经走过的点权和
        if(ans>maxx)
            maxx=ans;
        Dfs(p->n);
        ans-=y_v[p->n];
    }
}
void another()//处理新图
{
    int indeg[10020];//入度in-degree
    memset(indeg,0,sizeof(indeg));
    node *p;
    for(int i=1;i<=Index;i++)
        Tail[i]=&Head[i];
    for(int i=1;i<=n;i++)
    {
        p=&head[i];
        while(p->nxt!=NULL)
        {
            p=p->nxt;
            if(y_n[i]!=y_n[p->n])
            {
                Tail[y_n[i]]->nxt=new node(y_n[p->n]);
                Tail[y_n[i]]=Tail[y_n[i]]->nxt;
                indeg[y_n[p->n]]++;
            }
        }
    }
    for(int i=1;i<=Index;i++)
        if(indeg[i]==0)//只有度为0的才找,剪一部分枝
        {
            if(y_v[i]>maxx)
                maxx=y_v[i];
            ans=y_v[i];
            Dfs(i);
        }

}
int main()
{
    memset(in,0,sizeof(in));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    int m,u,V;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        tail[i]=&head[i];
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&V);//建原图
        tail[u]->nxt=new node(V);
        tail[u]=tail[u]->nxt;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            dfs(i);//缩点

    another();//建新图并处理
    printf("%d\n",maxx);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */