洛谷P3119/USACO15JAN 草鉴定Grass Cownoisseur

@Pelom  October 27, 2019

题意

给出一张有向图,可以逆行$1$次,求从$1$回到$1$最多经过几个点

数据范围:$1 \le n,m \le 100000$

题解

首先$\mathrm{Tarjan}$缩点,并将新点点权赋为所在强连通分量的点数
新图建分层图,连接两层之间为反向边,意为逆行$1$次
从$1$所在的强连通分量开始跑$\mathrm{SPFA}$最长路,答案即为到第二层中$1$所在的强连通分量对应的点的距离

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
const int N=100000+10;
stack<int> S;
int n,m,w;
int u[N],v[N];
int cnt,dep,tot;
int head[N<<1],dfn[N],low[N],clr[N],siz[N],dis[N<<1];
bool vis[N<<1];
struct edge{
    int nxt,to;
} e[N*3];
inline void add(int u,int v){
    e[++cnt]=edge{head[u],v};
    head[u]=cnt;
}
void Tarjan(int u){
    dfn[u]=low[u]=++dep;
    S.push(u);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!clr[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        tot++;
        for(int t=0;t!=u;){
            t=S.top();
            S.pop();
            clr[t]=tot;
            siz[tot]++;
        }
    }
}
inline void SPFA(int S){
    queue<int> Q;
    Q.push(S);
    vis[S]=1;
    for(;!Q.empty();){
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[v]<dis[u]+siz[u]){
                dis[v]=dis[u]+siz[u];
                if(!vis[v]){
                    Q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        add(u[i],v[i]);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            Tarjan(i);
    cnt=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=tot;i++)
        siz[i+tot]=siz[i];
    for(int i=1;i<=m;i++){
        if(clr[u[i]]==clr[v[i]])
            continue;
        add(clr[u[i]],clr[v[i]]);
        add(clr[u[i]]+tot,clr[v[i]]+tot);
        add(clr[v[i]],clr[u[i]]+tot);
    }
    add(clr[1],clr[1]+tot);
    SPFA(clr[1]);
    printf("%d",dis[clr[1]+tot]);
    return 0;
}

添加新评论