Description

每一头牛的愿望就是变成一头最受欢迎的牛. 现在有 \(n\) 头牛, 给你 \(m\) 对整数 \((A, B)\), 表示牛 \(A\) 认为牛 \(B\) 受欢迎. 这种关系是具有传递性的, 如果 \(A\) 认为 \(B\) 受欢迎,\(B\) 认为 \(C\) 受欢迎, 那么牛 \(A\) 也认为牛 \(C\) 受欢迎. 你的任务是求出有多少头牛被所有的牛认为是受欢迎的.

Input

第一行两个数 \(n, m\). 接下来 \(m\) 行, 每行两个数 \(A, B\), 意思是 \(A\) 认为 \(B\) 是受 欢迎的 (给出的信息有可能重复, 即有可能出现多个 \(A, B\))

Output

一个数, 即有多少头牛被所有的牛认为是受欢迎的.

Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

Data Range

100% 的数据 \(n \leq 10000, m \leq 50000\)

Explanation

此题强连通分量 Tarjan 水过......

然后把它看成一个 DAG (有向无环图), 若只有一个出度为 \(0\) 的点, 则这个点 (强连通分量) 所包含的所有点一定都是答案; 否则没有牛符合条件.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 10010, maxm = 50100;

class Tarjan
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    int n, ecnt;
    int bcnt, dcnt;
    int dfn[maxn], low[maxn];
    int belong[maxn], bsize[maxn];
    edge *edges[maxn], epool[maxm];
    stack<int> stk;
    bool instk[maxn];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    void dfs(int p)
    {
        dfn[p] = low[p] = ++dcnt;
        stk.push(p);
        instk[p] = true;
        for (edge *ep = edges[p]; ep; ep = ep->next) {
            int q = ep->v;
            if (!dfn[q]) {
                dfs(q);
                if (low[q] < low[p])
                    low[p] = low[q];
            } else if (instk[q] && dfn[q] < low[p]) {
                low[p] = dfn[q];
            }
        }
        if (dfn[p] == low[p]) {
            bcnt++; // Assign new belong / block counter index
            int q = 0;
            do {
                q = stk.top();
                stk.pop();
                instk[q] = false;
                belong[q] = bcnt;
                bsize[bcnt]++;
            } while (q != p);
        }
        return ;
    }
    void eval(void)
    {
        while (!stk.empty())
            stk.pop();
        bcnt = dcnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(instk, 0, sizeof(instk));
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                dfs(i);
        return ;
    }
    // Some other modifications
    // That does not belong to SCC Tarjan.
    int out_degree[maxn];
    void work_out_degree(void)
    {
        for (int p = 1; p <= n; p++)
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (belong[ep->v] != belong[p])
                    out_degree[belong[p]]++;
        return ;
    }
    int get_final_result(void)
    {
        work_out_degree();
        int res = 0;
        for (int i = 1; i <= bcnt; i++)
            if (!out_degree[i]) {
                if (res) return 0;
                res = bsize[i];
            }
        return res;
    }
} graph;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = n;
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        graph.add_edge(a, b);
    }
    graph.eval();
    int res = graph.get_final_result();
    printf("%d\n", res);
    return 0;
}