提交记录

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int dfn[N], low[N], stk[N], instk[N], scc[N], sz[N], tot, top, cnt;
int vis[N], dist[N], dist_reverse[N];
vector<int> adj[N];
vector<int> e[N];
vector<int> g[N];
vector<pair<int, int> > edge;

void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    instk[u] = 1;
    for (int i = 0; i < adj[u].size(); i++) {
        int j = adj[u][i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (instk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        int y;
        cnt++;
        do{
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            sz[cnt]++;
        }while(y != u);
    }
}

void spfa(int u) {
    queue<int> q;
    q.push(u);
    vis[u] = 1;
    dist[u] = sz[u];
    while(q.size()) {
        int t = q.front();
        q.pop();
        vis[t] = 0;
        for (int i = 0; i < e[t].size(); i++) {
            int j = e[t][i];
            if (dist[j] < dist[t] + sz[j]) {
                dist[j] = dist[t] + sz[j];
                if (!vis[j]) {
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }
}

void spfa_reverse(int u) {
    memset(vis, 0, sizeof vis);
    queue<int> q;
    q.push(u);
    vis[u] = 1;
    dist_reverse[u] = sz[u];
    while(q.size()) {
        int t = q.front();
        q.pop();
        for (int i = 0; i < g[t].size(); i++) {
            int j = g[t][i];
            if (dist_reverse[j] < dist_reverse[t] + sz[j]) {
                dist_reverse[j] = dist_reverse[t] + sz[j];
                if (!vis[j]) {
                    q.push(j);
                    vis[j] = 1;
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
    }
    for (int i = 1; i <= n; i++)    
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < adj[i].size(); j++) {
            int k = adj[i][j];
            if (scc[i] != scc[k]) {
                e[scc[i]].push_back(scc[k]);
                g[scc[k]].push_back(scc[i]);
                edge.push_back({scc[i], scc[k]});
            }
        }
    }
    spfa(scc[1]);
    spfa_reverse(scc[1]);
    int ans = sz[scc[1]];
    for (int i = 0; i < edge.size(); i++) {
        auto t = edge[i];
        if (dist[t.second] == 0 || dist_reverse[t.first] == 0) continue;
        ans = max(ans, dist[t.second]+dist_reverse[t.first]-sz[scc[1]]);
    }
    printf("%d\n", ans);
    return 0;
}