记录编号	514677	评测结果	AAAAAAAAAAAAAAAA
题目名称	膜拜	最终得分	100
用户昵称	jekyll	是否通过	通过
代码语言	C++	运行时间	0.162 s
提交时间	2018-10-17 08:43:52	内存使用	7.94 MiB

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
 
typedef pair<int, int> Pair;
const int maxn = 100005;
 
int n, m;
int head[maxn], rshead[maxn], shead[maxn], cnt;
struct Edge {
    int v, next;
} edge[maxn<<2];
 
inline void add_edge(int u, int v, int* head) {
    edge[++cnt] = (Edge) {v, head[u]};
    head[u] = cnt;
}
 
int scc, timec;
int stk[maxn], instk[maxn], ind;
int color[maxn], sum[maxn], dfn[maxn], low[maxn];
void tarjan(int u, int* head) {
    low[u] = dfn[u] = ++timec;
    stk[++ind] = u, instk[u] = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (!dfn[v])
            tarjan(v, head), low[u] = min(low[u], low[v]);
        else if (instk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++scc;
        do {
            sum[scc]++;
            color[stk[ind]] = scc;
            instk[stk[ind--]] = 0;
        } while (stk[ind+1] != u);
    }
}
 
int d[maxn], f[maxn], inque[maxn];
void SPFA(int _s, int* head, int* dis) {
    queue<int> que;
    for (int i = 1; i <= scc; i++)	
        dis[i] = 0, inque[i] = 0;
    dis[_s] = sum[_s]; que.push(_s);
    while (!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = 0;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (dis[v] < dis[u] + sum[v]) {
                dis[v] = dis[u] + sum[v];
                if (!inque[v]) que.push(v), inque[v] = 1;
            }
        }
    }
}
 
void GetSCC(int* head) {
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, head);
    for (int u = 1; u <= n; u++)
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (color[u] != color[v])
                add_edge(color[u], color[v], shead),
                add_edge(color[v], color[u], rshead);
        }
}
 
inline int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x<<1) + (x<<3) + (ch^48), ch = getchar();
    return x;
}
 
int main() {
	freopen("OrzOrz.in", "r", stdin);
	freopen("OrzOrz.out", "w", stdout);
 
    n = read(), m = read();
    for (int i = 1, a, b; i <= m; i++)
        a = read(), b = read(), add_edge(a, b, head);
 
    GetSCC(head);
    SPFA(color[1], shead, d);
    SPFA(color[1], rshead, f);
 
    int ans = 0;
    for (int u = 1; u <= scc; u++)
        for (int i = shead[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (d[v] && f[u]) ans = max(ans, d[v] + f[u]);
        }
    if (ans != sum[color[1]]) ans -= sum[color[1]];
    cout << ans << '\n';
 
    fclose(stdin), fclose(stdout);
    return 0;
}