缩点

#include <stdio.h>
#include <iostream>
#include <cstring>
const int maxn = 10e5+5;
using namespace std;
class stack {
        int a[maxn];
        int visit[maxn];
        int rare;
    public:
        void init() {
            memset(visit,0,sizeof(visit));
            rare= 0;
        }
    public:
        void push(int x) {
            visit[x] = 1;
            a[rare++] = x;
        }
    public:
        int pop() {
            int ret = a[--rare];
            visit[ret] = 0;
            return ret;
        }
    public:
        int isin(int x) {
            return visit[x];
        }
};
struct edge {
    int from,to;
} edges[maxn];
int in[maxn],head[maxn],nex[maxn],dis[maxn],q,diss[maxn];
inline void connect(int x,int y) {
    nex[++q] = head[x],dis[q] = y,head[x] = q;
}
stack s;
int time,dfn[maxn],low[maxn],scc,f[maxn],val[maxn];
void tarjan(int a) {
    dfn[a] = low[a] = ++time;
    s.push(a);
    for(int i = head[a]; i; i=nex[i]) {
        if(!dfn[dis[i]]) {
            tarjan(dis[i]);
            low[a] = min(low[a],low[dis[i]]);
        } else if(s.isin(dis[i])) low[a] = min(low[a],dfn[dis[i]]);
    }
    if(dfn[a]==low[a]) {
        scc++;
        do {
            a = s.pop();
            f[a] = scc;
            val[scc] ++;
        } while(dfn[a]!=low[a]);
    }
}
int que[maxn],rare,hh;
int main() {
    s.init();
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i<=m; i++) {
        int x,y;
        scanf("%d%d",&x,&y);    
        connect(y,x);
        edges[i].from = y,edges[i].to  = x;
    }
    int ans = 0;
    for(int i = 1; i<=n; i++) if(!dfn[i]) tarjan(i);
    memset(head,0,sizeof(head));
    memset(nex,0,sizeof(nex));
    memset(dis,0,sizeof(dis));
    q = 0;
    for(int i = 1; i<=m; i++)
        if(f[edges[i].from]!=f[edges[i].to]) {
            connect(f[edges[i].from],f[edges[i].to]);
            in[f[edges[i].to]]++;
        }
    for(int i = 1;i<=scc;i++){
        if(in[i]==0){
            diss[i] = val[i];
            ans = max(ans,val[i]);
            que[rare++] = i;
        }
    }
    
    while(hh<rare){
        int a = que[hh++];
        for(int i = head[a];i;i = nex[i]){
            int to = dis[i];
            diss[to] = max(diss[to],diss[a]+val[to]);
            ans = max(ans,diss[to]);
            in[to]--;
            if(in[to]==0){
                que[rare++] = to;
            }
        }
    }
    cout<<ans;
    return 0;
}

这个九十五分，我也不知道怎么办了。话说我的代码比楼下takami的长得帅！

#include<bits/stdc++.h>
inline void read(int&a)
{
    a=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
        a=(a<<1)+(a<<3)+c-'0';
        c=getchar();
    }
}
inline void write(int a)
{
    if(a<0){putchar('-');a=-a;}
    if(a>9)write(a/10);
    putchar(a%10+'0');
}
const int maxn=1e6+1;
int next1[maxn],dfn[maxn],low[maxn],to1[maxn],point1[maxn],from1[maxn];
int n,m,r=0,d=0;
bool vis[maxn];
inline void add1(int a,int b)
{
    next1[++r]=point1[a];
    to1[r]=b;from1[r]=a;
    point1[a]=r;
}
int in[maxn],next[maxn],to[maxn],point[maxn],from[maxn];
inline void add(int a,int b)
{
    ++in[b];
    next[++d]=point[a];
    to[d]=b;
    point[a]=d;
}
int tt,f[maxn],ans=0;
int stack[maxn],belong[maxn],end=0,value[maxn];
bool in_stack[maxn];
inline void tarjan(int p)
{
    
    vis[p]=true;
    dfn[p]=low[p]=++tt;
    //value[p]=1;
    int side=point1[p];
    while(side)
    {
        if(!vis[to1[side]])
        {
            stack[++end]=to1[side];
            in_stack[to1[side]]=true;
            tarjan(to1[side]);
            low[p]=std::min(low[p],low[to1[side]]);
        }
        else if(in_stack[to1[side]])
        {
            low[p]=std::min(low[p],low[to1[side]]);
        }
        side=next1[side];
    }
    if(dfn[p]==low[p])
    {
        while(stack[end]!=p)
        {
            belong[stack[end]]=p;
            in_stack[stack[end]]=false;
            value[p]+=value[stack[end]];
            --end;
        }
        belong[p]=p;
        in_stack[p]=false;
        --end;
    }
}
inline void dfs(int p)
{
//  write(p);putchar(' ');
    int side=point[p];
    while(side)
    {
        if(f[p]+value[to[side]]>f[to[side]])
            {f[to[side]]=f[p]+value[to[side]];dfs(to[side]);}
        side=next[side];
    }
}
int main()
{
    read(n);read(m);
    memset(in,0,sizeof(in));
    memset(value,0,sizeof(value));
    memset(in_stack,false,sizeof(in_stack));
    memset(vis,false,sizeof(vis));
    memset(point1,0,sizeof(point1));
    int u,v;
    for(int i=1;i<=n;i++)value[i]=1;
    for(int i=1;i<=m;i++)
    {
        read(u);read(v);
        add1(u,v);
    }
    tt=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            stack[++end]=i;in_stack[i]=true;
            tarjan(i);
        }
    }
    for(int i=1;i<=r;i++)if(belong[from1[i]]!=belong[to1[i]])add(belong[from1[i]],belong[to1[i]]);
    for(int i=1;i<=n;i++)if(!in[i]&&belong[i]==i){f[i]=value[i];dfs(i);}//puts("dd");
    for(int i=1;i<=n;i++)ans=std::max(ans,f[i]);
    write(ans);
    return 0;
}