题解

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m;
cin >> n >> m;

vector<int> next(n + 1, 0);   // 记录每个节点的后继节点
vector<int> prev(n + 1, 0);   // 记录每个节点的前驱节点
vector<int> in_degree(n + 1, 0);  // 入度
vector<int> out_degree(n + 1, 0); // 出度

bool possible = true;

for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;

    // 检查是否存在矛盾的约束
    if (next[a] != 0 && next[a] != b) {
        possible = false;
    }
    if (prev[b] != 0 && prev[b] != a) {
        possible = false;
    }

    next[a] = b;
    prev[b] = a;
    out_degree[a]++;
    in_degree[b]++;

    // 检查是否有节点出度大于1
    if (out_degree[a] > 1) {
        possible = false;
    }
}

if (!possible) {
    cout << 0 << endl;
    return 0;
}

// 检查是否存在环
vector<int> temp_in = in_degree;
queue<int> q;

// 初始入度为0的节点入队
for (int i = 1; i <= n; ++i) {
    if (temp_in[i] == 0) {
        q.push(i);
    }
}

int cnt = 0;
while (!q.empty()) {
    int u = q.front();
    q.pop();
    cnt++;
    int v = next[u];
    if (v != 0) {
        temp_in[v]--;
        if (temp_in[v] == 0) {
            q.push(v);
        }
    }
}

if (cnt != n) {
    cout << 0 << endl;
    return 0;
}

// 计算连通分量的数量
int components = 0;
vector<bool> visited(n + 1, false);
for (int i = 1; i <= n; ++i) {
    if (prev[i] == 0 && !visited[i]) {  // 找到每个连通分量的起点
        components++;
        int current = i;
        while (current != 0) {
            visited[current] = true;
            current = next[current];
        }
    }
}

// 计算components! mod MOD
long long result = 1;
for (int i = 2; i <= components; ++i) {
    result = (result * i) % MOD;
}

cout << result << endl;

return 0;

}