题目链接：Grass Cownoisseur

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently numbered 1..N, with each one-way cow path connecting a pair of fields. For example, if a path connects from field X to field Y, then cows are allowed to travel from X to Y but not from Y to X. Bessie the cow, as we all know, enjoys eating grass from as many fields as possible. She always starts in field 1 at the beginning of the day and visits a sequence of fields, returning to field 1 at the end of the day. She tries to maximize the number of distinct fields along her route, since she gets to eat the grass in each one (if she visits a field multiple times, she only eats the grass there once). As one might imagine, Bessie is not particularly happy about the one-way restriction on FJ's paths, since this will likely reduce the number of distinct fields she can possibly visit along her daily route. She wonders how much grass she will be able to eat if she breaks the rules and follows up to one path in the wrong direction. Plea***pute the maximum number of distinct fields she can visit along a route starting and ending at field 1, where she can follow up to one path along the route in the wrong direction. Bessie can only travel backwards at most once in her journey. In particular, she cannot even take the same path backwards twice.
输入描述:
The first line of input contains N and M, giving the number of fields
and the number of one-way paths (1 <= N, M <= 100,000).
The following M lines each describe a one-way cow path. Each line
contains two distinct field numbers X and Y, corresponding to a cow
path from X to Y. The same cow path will never appear more than once.
输出描述:
A single line indicating the maximum number of distinct fields Bessie
can visit along a route starting and ending at field 1, given that she can
follow at most one path along this route in the wrong direction.
输入

输出

Bessie can visit pastures 1, 2, 4, 7, 2, 5, 3, 1 by traveling
backwards on the path between 5 and 3. When she arrives at 3 she
cannot reach 6 without following another backwards path.

题目大意

有n个草坪，m条有向边，现在让你从1号顶点开始出发，最后还要回到1号顶点，其中你可以逆向走一次，每个条边可以走多次，但是每个草坪只能吃一次，问你最多可以吃几个草坪；

解题思路

这个题，我们首先想到先缩点，因为如果是个环的话，我们可以绕着这个环走一圈走到这个环的任意一个节点，因此我们可以考虑用tarjan缩点，然后得到一个树形图，这时候我们再将这个树形图反向存一遍，这是为了解决1—>2—>3，4—>1，4—>3；这样的话其实我们可以反向跑一遍缩点后的图，将可以跑到的点标记出来，再正向跑树形图的时候如果这个顶点所连接的节点有被标记过得，那么我们就更新一下最大值，如果没有就不用管，当让还有一些细节，比如说缩完点后1这个节点是最下面的一个，比如说 n=4，m=4；3—>1,3—>2,2—>1,1—>4我们需要第一次反向走才行，那么我就要先预处理一下直接从1开始反方向走结果的最大值，事先更新最后的结果是3。大致思路有了可以开始码了。

代码

#include<bits/stdc++.h>
using namespace std;
const int MX=1e5+10;
int n,m,cnt;
int dfn[MX],low[MX];//tarjan 记录第几个被遍历到的和最近的遍历节点 
int color[MX],color_num[MX];//该节点属于什么颜色，该颜色有多少个节点 
vector<int>ve[MX],ve1[MX],ve2[MX];//分别存原数据，缩完点后的反向图，缩完点后的正向图 
bool vis[MX],f[MX];//分别表示是否在栈中，是否可以走到 1号节点 
int sum;//一共有几种颜色 
stack<int>st;
int ans[MX];//走到这个节点最多可以吃多少草 
int max_op=0;//当前最多可以吃多少草 

void tarjan(int u)//tarjan缩点模板，没有改动 
{
    dfn[u]=low[u]=++cnt;
    st.push(u);//放入栈中 
    vis[u]=1;//标记 
    for(int v:ve[u])
    {
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    int k;
    if(low[u]==dfn[u])
    {
        sum++;
        do{
            k=st.top();st.pop();
            color[k]=sum;//该节点属于什么颜色 
            color_num[sum]++;//该颜色数量加一 
            vis[k]=0;
        }while(k!=u&&!st.empty());
    }
}
void bfs1(int x)//逆向跑图 
{
    queue<int>qu;
    qu.push(x);
    f[x]=1;
    while(!qu.empty())
    {
        int u=qu.front();qu.pop();
        for(int v:ve1[u])
        {
            if(ans[u]+color_num[v]>ans[v])//如果这次走到这个节点吃的更多就更新 
            {
                ans[v]=ans[u]+color_num[v];//更新这个点可以吃的最大值 
                f[v]=1;//因为逆向可以走到这个节点 
                qu.push(v);//说明这个节点正向可以走到 1 所以标记一下 
            }
        }
    }
}
int check(int x)//检查这个节点所连接的节点逆向走一次有没有可以最终走到1号节点的 
{
    int S=0;
    for(int i:ve1[x])
    {
        if(f[i]) S=max(S,ans[i]);//更新这些节点中最大的一个 
    }
    return S;
}
void bfs2(int x)
{
    queue<int>q;
    q.push(x);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v:ve2[u])    
        {
            if(ans[v]<ans[u]+color_num[v])//和逆向构图一样 
            {
                ans[v]=ans[u]+color_num[v];//更新最大值 
                int K=check(v);//检查这个节点是否可以逆着走一次回到1 
                if(K)//能的话更新最大值，否则不更新 
                max_op=max(max_op,ans[v]+K);
                q.push(v);
            }
        }
    }
}
int main()
{
//    freopen("123.in","r",stdin); //1952
    cin>>n>>m;
    for(int i=0,x,y;i<m;i++)
    {
        cin>>x>>y;
        ve[x].push_back(y);
    }
    for(int i=1;i<=n;i++)//tarjan缩点 
    {
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++)//根据染完色后的图重新构图 
    {
//************************这里很重要，不理解的可以自己画个有向带环图理解下******************** 
        for(int v:ve[i])
        {
            if(color[i]!=color[v])//如果这个个相连的节点不是一个颜色就重新构图 
            {
                ve2[color[i]].push_back(color[v]);//正向构图，i节点对应的颜色指向v节点的颜色 
                ve1[color[v]].push_back(color[i]);//反向构图 
            }
        }
    }
//将 1号 节点对应的颜色有几个节点实现赋值 
    ans[color[1]]=color_num[color[1]];
    bfs1(color[1]);//逆向遍历 
    for(int i:ve1[color[1]]) 
    {    
        max_op=max(ans[i],max_op);//遍历如果先逆向走一次最大可以吃几个草坪 
    }
    max_op+=color_num[color[1]];//这里要再加一下第一个，最后减去方便后面的计算 
    bfs2(color[1]);//正向遍历 
    cout<<max_op-color_num[color[1]]<<'\n';//输出答案 
    return 0;
}