拓撲排序最長鏈-P3119 [USACO15JAN]草鑒定Grass Cownoisseur

https://www.luogu.org/problem/show?pid=3119
本來我是來練習tarjan的，結果tarjan部分直接copy了，反而拓撲排序部分想了好久；
這道題SZB大神兩次就AC；
但我等到AC，寫好題解就只能洗洗睡了；
唉~
差距怎么這么大呢？；
這道題的題意就說，你可以改變一條邊的方向，去找到一個環，讓環上的點數最大；
網上的題解，大多都在嚷嚷tarjan+拓撲排序最長鏈；
我先講講什么是拓撲排序最長鏈把；

---

很顯然啊，上面的圖里，1~3的最長鏈是3；
我們考慮一下最樸素的dfs;
我們從1開始，先搜索到了3；
這個時候我們把1~3的最長鏈更新為 1-3，就是2個節點；
假如3出度有好多，那么凡是3后面的點我們都要遍歷一邊；
然后遍歷完3，我發現 1~3的最長鏈不是1-3而是1-2-3;
原先的1~3最長鏈的節點個數2被更新為3；
這個時候我們發現原來3連出去的點，他們與1的最長鏈都不是最優的;
所以我們又要dfs一遍；
這樣太煩了；
那怎么辦呢？
看到這里，我想您一定知道什么是拓撲排序最長鏈了；
對啊，假如我們搜索到3的時候先不去往后面搜索，先去遍歷2；
這樣1~3的最長鏈會被及時更新，3后面的節點就不用重復更新了；
其實這樣就是按照拓撲排序的順序去遍歷節點啊，不斷找入度為0的節點去更新其它節點；
這就是拓撲排序最長鏈

---

這道題就簡單了啊；
我先縮點一下，讓這個有環圖變成有向無環圖；
然后用一個dfs去算出那些點可以到達1；那些點會從1到達；
分別算出這些點到1的最長鏈，然后枚舉每一條邊，看看把這條邊反一下，加上兩端到1的最長鏈然后更新ans就好啦；
很顯然啊，這兩條鏈不會重復，因為他們的方向是不同的；
我的超級優美的代碼，60行！；

超級無敵大壓行！！！！

#include<cstdio>//cfb
#include<iostream>
#include<cstring>
using namespace std;
struct cs{int to,next;}a[100001];          //lin[i]是i再那個分量里面  sum[i]就是第i個分量有幾個點 d[i]是當前分量i的入度 
int head[100001],low[100001],tt[100001],q[100001],lin[100001],cc[100001][2],sum[100001],A[100001][1],d[100001];
bool in[100001],AA[100001][2];//AA[i][0]表示1是否可以到i，[1]是i是否可以到j;A[i][0/1]即他們的最長鏈 
int ll,n,m,x,y,z,t,nn,l,r,ans;
void init(int x,int y){a[++ll].to=y; a[ll].next=head[x]; head[x]=ll;}
void dfs(int x){
    tt[x]=++t; low[x]=t; q[++q[0]]=x; in[x]=1;
    for(int k=head[x];k;k=a[k].next){
        if(!tt[a[k].to])dfs(a[k].to);
        if(in[a[k].to])low[x]=min(low[x],low[a[k].to]); 
    }
    if(low[x]==tt[x]){
        nn++;
        while(1){
            in[q[q[0]]]=0;
            lin[q[q[0]]]=nn;    
            q[0]--; sum[nn]++;
            if(q[q[0]+1]==x)break;
        }
    }
}
void make(int x,int num){//然后用一個dfs去算出那些點可以到達1；那些點會從1到達；
    in[x]=1; AA[x][num]=1;
    for(int k=head[x];k;k=a[k].next){d[a[k].to]++; if(!in[a[k].to])make(a[k].to,num);}
}
void TP(int num){//拓撲排序
    r=1; q[1]=lin[1]; A[lin[1]][num]=0; 
    make(lin[1],num); 
    while(r>l){
        x=q[++l];
        for(int k=head[x];k;k=a[k].next){
            A[a[k].to][num]=max(A[a[k].to][num],A[x][num]+sum[a[k].to]);
            d[a[k].to]--;
            if(!d[a[k].to])q[++r]=a[k].to;
        }
    }
}
void S(){
    memset(q,0,sizeof q);memset(head,0,sizeof head);
    memset(d,0,sizeof d);memset(in,0,sizeof in);
    ll=0; r=l=0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){scanf("%d%d",&cc[i][0],&cc[i][1]);init(cc[i][0],cc[i][1]);}
    for(int i=1;i<=n;i++)if(!tt[i])dfs(i);
    S(); for(int i=1;i<=m;i++){x=cc[i][0]; y=cc[i][1]; if(lin[x]!=lin[y])init(lin[x],lin[y]);} TP(0);
    S(); for(int i=1;i<=m;i++){x=cc[i][0]; y=cc[i][1]; if(lin[x]!=lin[y])init(lin[y],lin[x]);} TP(1);
    for(int i=1;i<=m;i++){
        x=lin[cc[i][0]]; y=lin[cc[i][1]];
        if(x==y||!AA[y][0]||!AA[x][1])continue;
        ans=max(ans,A[y][0]+A[x][1]);
    }
    printf("%d",ans+sum[lin[1]]);
}