洛谷3119 草鉴定Grass Cownoisseur

题意

给出一个 $n$ 点 $m$ 边的有向图，从 $1$ 出发再回到 $1$ ，途中要逆行一次，问途中最多经过多少个点。

$n,m\le 10^{5}$ 。

题解

显然要缩点，缩点后点权即为连通分量中点的个数 $\text{siz[]}$ 。

然后对强连通分量重新建边，正边为 $\text{edge2}$ ，反边为 $\text{edge3}$ 。对正边跑最长路得到以 $1$ 为起点的最长路 $\text{dis1[]}$ ，反边得到以 $1$ 为终点的最长路 $\text{dis2[]}$。

最后枚举逆行那条边的起点 $x$ 和终点 $y$ ，则逆行边 $edge3(x,y)$ 的答案即为 $dis1[x]+dis2[y]-siz[1]$ （$1$ 被重复算了所以减掉）。

注意需要保证 $x$ 和 $y$ 是可达 $1$ 的，即 $dis1[x]\neq 0 \ , \ dis2[y]\neq 0$ 。

#include<bits/stdc++.h>
#define N 100005

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[N],edge2[N],edge3[N];
bool inq[N];
stack <int> s;
int scc[N],siz[N],id[N],low[N],dfsord,scnt;
int cnt,cnt2,cnt3,head[N],head2[N],head3[N],dis1[N],dis2[N],n,m,a,b,ans;

void tarjan(int x);
inline void spfa1(int st);
inline void spfa2(int st);
inline void add(int u,int v);
inline void add2(int u,int v);
inline void add3(int u,int v);

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
    }
    for (int i=1;i<=n;i++)
    {
        if (id[i]) continue;
        tarjan(i);
    }
    for (int x=1;x<=n;x++)
    {
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if (scc[x]==scc[y]) continue;
            add2(scc[x],scc[y]);
            add3(scc[y],scc[x]);
        }
    }
    spfa1(scc[1]);
    spfa2(scc[1]);
    ans=siz[scc[1]];
    for (int x=1;x<=scnt;x++)
    {
        if (!dis1[x]) continue;
        for (int j=head3[x];j;j=edge3[j].next)
        {
            int y=edge3[j].to;
            if (!dis2[y]) continue;
            ans=max(ans,dis1[x]+dis2[y]-siz[scc[1]]);
        }
    }
    printf("%d",ans);
    return 0;
}

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void add2(int u,int v)
{
    edge2[++cnt2].to=v;
    edge2[cnt2].next=head2[u];
    head2[u]=cnt2;
}

inline void add3(int u,int v)
{
    edge3[++cnt3].to=v;
    edge3[cnt3].next=head3[u];
    head3[u]=cnt3;
}

void tarjan(int x)
{
    id[x]=low[x]=++dfsord;
    s.push(x);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            siz[scnt]++;
            if (t==x) break;
        }
    }
}

inline void spfa1(int st)
{
    memset(inq,0,sizeof(inq));
    queue <int> q;
    q.push(st);
    dis1[st]=siz[st];
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        inq[x]=0;
        for (int i=head2[x];i;i=edge2[i].next)
        {
            int y=edge2[i].to;
            if (dis1[x]+siz[y]>dis1[y])
            {
                dis1[y]=dis1[x]+siz[y];
                if (inq[y]) continue;
                q.push(y);
                inq[y]=1;
            }
        }
    }
}

inline void spfa2(int st)
{
    memset(inq,0,sizeof(inq));
    queue <int> q;
    q.push(st);
    dis2[st]=siz[st];
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        inq[x]=0;
        for (int i=head3[x];i;i=edge3[i].next)
        {
            int y=edge3[i].to;
            if (dis2[x]+siz[y]>dis2[y])
            {
                dis2[y]=dis2[x]+siz[y];
                if (inq[y]) continue;
                q.push(y);
                inq[y]=1;
            }
        }
    }
}