GESP-C++八级 题库
在C++中,若结构体中包含一个 static 成员变量,则该变量的存储空间属于结构体对象的一部分。( )
在C++中,若函数参数类型为 const int & ,则该参数既可以绑定左值,也可以绑定右值。( )
若一个无向图的最小生成树唯一,则图中所有边权必定各不相同。( )
若一个图中所有顶点的度数为偶数,则一定存在欧拉回路。( )
如果将一个连通无向图
中所有边的权值都统一增加同一个正整数常数C,形成图
。则
的最小生成树中每条边在
中对应的边组成的树,一定是
的最小生成树。( )
在图论算法中,Kruskal算法和Prim算法都可以用来求解最小生成树,且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。( )
在动态规划问题中,“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式,它们的时间复杂度总是相同的。( )
使用倍增法预处理区间最值问题时,预处理的时间复杂度为O(nlogn),查询的时间复杂度为O(1)。( )
猫和老鼠
时间限制:1.0 s
内存限制:512.0 MB
题目描述
猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2,...,n编号,结点i(1≤i≤n)有价值为ci的奶酪。在m条带权无向边中,第i(1≤i≤m)条无向边连接结点ui与结点vi,边权wi表示猫和老鼠通过这条边所需的时间。
猫窝位于结点a,老鼠洞位于结点b。对于老鼠而言,结点u是安全的当且仅当:
老鼠能规划一条从结点u出发逃往老鼠洞的路径,使得对于路径上任意结点x(包括结点u与老鼠洞)都有:
猫从猫窝出发到结点x的最短时间严格大于老鼠从结点u沿这条路径前往结点x所需的时间。
老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能,但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失,老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。
输入格式
第一行,两个正整数n,m,分别表示图的结点数与边数。
第二行,两个正整数a,b,分别表示猫窝的结点编号,以及老鼠洞的结点编号。
第三行,n个正整数c1,c2,...,cn,表示各个结点的奶酪价值。
接下来 行中的第i行(1≤x≤m)包含三个正整数ui,vi,wi,表示图中连接结点ui与结点vi的边,边权为wi。
输出格式
输出一行,一个整数,表示老鼠所能拿到的奶酪价值之和。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围
对于40的测试点,保证1≤n≤500,1≤m≤500。
对于所有测试点,保证1≤n≤105,1≤m≤105,1≤a,b≤n且a≠b,1≤ui,vi≤n,1≤wi≤109。
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 5;
const long long oo = 1e18;
int n, m;
int a, b;
int c[N];
vector<pair<int, int>> e[N];
long long dis[N];
priority_queue<pair<long long, int>> q;
long long ans;
int main() {
scanf("%d%d", &n, &m);
scanf("%d%d", &a, &b);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].emplace_back(make_pair(v, w));
e[v].emplace_back(make_pair(u, w));
}
for (int i = 1; i <= n; i++)
dis[i] = oo;
dis[b] = 0;
q.push(make_pair(-dis[b], b));
while (!q.empty()) {
auto p = q.top();
q.pop();
if (dis[p.second] != -p.first)
continue;
int u = p.second;
for (auto r : e[u]) {
int v = r.first, w = r.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(make_pair(-dis[v], v));
}
}
}
for (int i = 1; i <= n; i++)
if (dis[i] < dis[a])
ans += c[i];
printf("%lld\n", ans);
return 0;
}宝石项链
时间限制:1.0 s
内存限制:512.0 MB
题目描述
小 A 有一串包含n枚宝石的宝石项链,这些宝石按照在项链中的顺序依次以1,2,...,n编号,第n枚宝石与第1枚宝石相邻。项链由m种宝石组成,其中第i枚宝石种类为ti。
小 A 想将宝石项链分给他的好朋友们。具体而言,小 A 会将项链划分为若干连续段,并且需要保证每段都包含全部种宝石。请帮小 A 计算在满足条件的前提下,宝石项链最多可以划分为多少段。
输入格式
第一行,两个正整数n,m,分别表示宝石项链中的宝石的数量与种类数。
第二行,n个正整数ti,t2,...,tn,表示每枚宝石的种类。
输出格式
输出一行,一个整数,表示宝石项链最多可以划分的段数。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围

#include <cstdio>
#include <algorithm>
using namespace std;
const int L = 20;
const int N = 2e5 + 5;
const int oo = 1e9;
int n, m;
int t[N], jump[L][N];
int cnt[N], tot;
int ans;
int go(int u) {
int cnt = 0, ans = 0;
for (int i = L - 1; i >= 0; i--)
if (cnt + jump[i][u] <= n) {
cnt += jump[i][u];
ans += 1 << i;
u = (u + jump[i][u] - 1) % n + 1;
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
t[i + n] = t[i];
}
for (int i = 1, r = 0; i <= n; i++) {
while (tot < m) {
r++;
if (!cnt[t[r]]++)
tot++;
}
jump[0][i] = r - i + 1;
if (!--cnt[t[i]])
tot--;
}
for (int i = 1; i < L; i++)
for (int j = 1; j <= n; j++) {
int tar = (j + jump[i - 1][j] - 1) % n + 1;
jump[i][j] = min(jump[i - 1][j] + jump[i - 1][tar], oo);
}
for (int i = 1; i <= n; i++)
ans = max(ans, go(i));
printf("%d\n", ans);
return 0;
}最短距离



#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 100005;
int n, p, q;
int a, b;
int ans;
// 欧几里得求最大公约数
int gcd(int a, int b) {
if (!a || !b)
return a + b;
return gcd(b, a % b);
}
int main() {
scanf("%d%d%d", &n, &p, &q);
while (n--) {
scanf("%d%d", &a, &b);
if (a == b) {
ans = 0;
} else if (a == 1 || b == 1) {
ans = p;
} else {
// 两种拆分方案:各自单独处理
ans = min(p + p, q + q);
if (gcd(a, b) == 1) {
// 互质,可以合并处理花费p
ans = min(ans, p);
} else {
// 不互质,合并处理花费q
ans = min(ans, q);
}
}
printf("%d\n", ans);
}
return 0;
}最小生成树



#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005;
const int M = 200005;
const long long INF = 1e18;
int n, m;
// 存每条边两端点、权值、边编号数组
int u[M], v[M], w[M], p[M];
// 链式前向星:h表头,id存边编号,nx下一条边,et边计数
int h[N], id[M], nx[M], et;
// 并查集父数组f,mark标记是否是最小生成树树边
int f[N], mark[M];
long long sum_mst, ans[M];
// dep深度,pid记录到达该点的树边编号
int dep[N], pid[N];
// 按边权从小到大排序
bool cmp(int x, int y) {
return w[x] < w[y];
}
// 带路径压缩并查集查找,0代表根节点
int getf(int u) {
if (!f[u]) return u;
return f[u] = getf(f[u]);
}
// 链式前向星加边:x连接编号为p的边
void link(int x, int edge_id) {
id[++et] = edge_id;
nx[et] = h[x];
h[x] = et;
}
// DFS遍历最小生成树,求每个点深度、记录到达当前点的树边pid[x]
void dfs(int x, int fa = 0, int edge_id = 0) {
dep[x] = dep[fa] + 1;
pid[x] = edge_id;
for (int i = h[x]; i; i = nx[i]) {
// 异或快速求对端:u^v^x 得到另一个端点
int to = u[id[i]] ^ v[id[i]] ^ x;
if (to != fa) {
dfs(to, x, id[i]);
}
}
}
int main() {
scanf("%d%d", &n, &m);
// 读入所有边
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &u[i], &v[i], &w[i]);
p[i] = i;
}
// Kruskal:边按权升序
sort(p + 1, p + m + 1, cmp);
// 1. Kruskal构建最小生成树
for (int i = 1; i <= m; ++i) {
int eid = p[i];
int x = u[eid], y = v[eid];
int fx = getf(x), fy = getf(y);
if (fx == fy) continue;
// 选为树边,标记并累加MST总权值
mark[eid] = 1;
f[fx] = fy;
sum_mst += w[eid];
// 加入MST链式前向星
link(x, eid);
link(y, eid);
}
// 初始化答案:树边暂设无穷INF,非树边初始答案就是MST总和sum_mst
for (int i = 1; i <= m; ++i) {
ans[i] = mark[i] ? INF : sum_mst;
}
// DFS求MST上每个点深度、对应树边pid
dfs(1);
// 重置并查集,用于按非树边更新树边答案
for (int i = 1; i <= n; ++i) f[i] = 0;
// 2. 遍历所有非树边,更新路径上树边的替换答案
for (int i = 1; i <= m; ++i) {
int eid = p[i];
if (mark[eid]) continue; // 跳过树边,只处理非树边
int x = getf(u[eid]), y = getf(v[eid]);
// 向上爬LCA路径,统一路径上所有树边的答案
while (x != y) {
// 保证x更深
if (dep[x] < dep[y]) swap(x, y);
// pid[x]是连接x与父节点的树边
int tree_edge = pid[x];
// 替换这条树边后的新MST权值
ans[tree_edge] = sum_mst - w[tree_edge] + w[eid];
// 并查集向上合并,下次不再处理这条边
int to = u[tree_edge] ^ v[tree_edge] ^ x;
f[x] = to;
x = getf(x);
}
}
// 输出每条边答案:INF代表无法替换,输出-1;否则输出替换后最小生成树权值
for (int i = 1; i <= m; ++i) {
if (ans[i] < INF) printf("%lld\n", ans[i]);
else printf("-1\n");
}
return 0;
}树上旅行
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 n 个结点的有根树,结点依次以 1、2、……、n 编号,其中根结点的编号为 1。
小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先会选定结点 si 作为起点,并移动若干次。移动分为以下两种:
(1)移动至当前结点的父结点。特殊地,如果当前位于根结点,则不进行移动。
(2)移动至当前结点的所有子结点中编号最小的结点。特殊地,如果当前位于叶子结点,则不进行移动。
由于移动次数可能很大,对于第 i 次旅行,旅行中的移动将以 ki 个不为零的整数构成的序列 ai,1、ai,2、……、ai,k 表示。
对于 ai,j,若 ai,j > 0 则代表进行 ai,j 次第一种移动;若 ai,j < 0 则代表进行 ai,j 次第二种移动。根据给出的序列从左至右完成所有移动后,小 A 所在的结点即是旅行的终点。
给定每次旅行的起点与移动序列,请你求出旅行终点的结点编号。
【输入描述】
第一行,两个正整数 n、q,分别表示有根树的结点数量,以及旅行次数。
第二行,n -1 个整数 p2、p3、……、pn,其中 pi 表示结点 i 的父结点编号。
接下来 2q 行中的第 2i - 1行(1<=i<=q )包含两个正整数 si、ki,分别表示第 i 次旅行的起点编号,以及移动序列的长度。
第 2i 行包含 k 个整数 ai,1、ai,2、……、ai,k,表示移动序列。
【输出描述】
输出共 q 行,第 i 行包含一个整数,表示第 i 次旅行终点的结点编号。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】

对于所有测试点,保证 1 <= n <= 10^5,1 <= q <= 2×10^4,1 <= pi、si <= n,ki >= 1,且Σki <= 10^5,1<=|ai,j|<=n。
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
const int L = 18;
int n, q;
int h[N], nx[N];
int par[L][N], son[L][N];
void dfs(int u) {
for (int i = 1; i < L; i++)
par[i][u] = par[i - 1][par[i - 1][u]];
son[0][u] = u;
for (int i = h[u]; i; i = nx[i]) {
dfs(i);
if (son[0][u] == u || i < son[0][u])
son[0][u] = i;
}
for (int i = 1; i < L; i++)
son[i][u] = son[i - 1][son[i - 1][u]];
}
int move(int go[L][N], int u, int step) {
for (int i = 0; i < L; i++)
if ((step >> i) & 1)
u = go[i][u];
return u;
}
int main() {
cin >> n >> q;
for (int i = 2; i <= n; i++) {
cin >> par[0][i];
nx[i] = h[par[0][i]];
h[par[0][i]] = i;
}
par[0][1] = 1;
dfs(1);
while (q--) {
int s, k;
cin >> s >> k;
while (k--) {
int a;
cin >> a;
if (a < 0)
s = move(son, s, -a);
else
s = move(par, s, a);
}
cout << s << endl;
}
return 0;
}遍历计数
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 n 个结点的树 T,结点依次以 1、2、……、n 标号。树 T 的深度优先遍历序可由以下过程得到:
(1)选定深度优先遍历的起点 s(1<=s<=n ),当前所在结点即是起点。
(2)若当前结点存在未被遍历的相邻结点 u 则遍历 u,也即令当前所在结点为 u 并重复这一步;否则回溯。
(3)按照遍历结点的顺序依次写下结点编号,即可得到一组深度优先遍历序。
第一步中起点的选择是任意的,并且第二步中遍历相邻结点的顺序是任意的,因此对于同一棵树 T 可能有多组不同的深度优先遍历序。
请你求出树 T 有多少组不同的深度优先遍历序。由于答案可能很大,你只需要求出答案对 10^9 取模之后的结果。
【输入描述】
第一行,一个整数 n,表示树 T 的结点数。
接下来 n - 1 行,每行两个正整数 ui、vi,表示树 T 中的一条连接结点 ui、vi 的边。
【输出描述】
输出一行,一个整数,表示树 的不同的深度优先遍历序数量对 10^9 取模的结果。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于40%的测试点,保证 1 <= n <= 8。
对于另外20%的测试点,保证给定的树是一条链。
对于所有测试点,保证 1 <= n <= 100000。
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9;
int n, deg[N], fac[N];
int pre[N], suf[N], ans;
int main() {
cin >> n;
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
}
pre[0] = 1;
for (int i = 1; i <= n; i++)
pre[i] = 1ll * pre[i - 1] * fac[deg[i] - 1] % mod;
suf[n + 1] = 1;
for (int i = n; i; i--)
suf[i] = 1ll * suf[i + 1] * fac[deg[i] - 1] % mod;
for (int i = 1; i <= n; i++)
ans = (ans + 1ll * pre[i - 1] * fac[deg[i]] % mod * suf[i + 1]) % mod;
cout << ans << endl;
return 0;
}上学
时间限制:1 s,内存限制:512 MB
【问题描述】
C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1、2、……、n 标号,边依次以 1、2、……、m 标号。
第 i 条边(1<=i<=m)连接编号为 ui 与 vi 的结点,长度为 li 米。
小 A 的学校坐落在 C 城中编号为 s 的结点。小 A 的同学们共有 q 位,他们想在保证不迟到的前提下,每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校,于是找到了聪明的小 A。
第 i 位同学(1<=i<=q )告诉小 A,他的家位于编号为 hi 的结点,并且他每秒能行走 1 米。请你帮小 A 计算,每位同学从家出发需要多少秒才能到达学校呢?
【输入描述】
第一行,四个正整数 n、m、s、q,分别表示 C 城的结点数与边数,学校所在的结点编号,以及小 A 同学们的数量。
接下来 m 行,每行三个正整数 ui、vi、li,表示 C 城中的一条无向边。
接下来 q 行,每行一个正整数 hi,表示一位同学的情况。
【输出描述】
共 q 行,对于每位同学,输出一个整数,表示从家出发到学校的最短时间。
【样例输入1】
【样例输出1】
【数据范围】
对于 20% 的测试点,保证 q=1。
对于另外 20% 的测试点,保证 1<=n<=500,1<=m<=500 。
对于所有测试点,保证 1<=n<=2×10^5,1<=m<=2×10^5 ,1<=q<=2×10^5 ,1<=ui、vi、hi<=n ,1<=li<=10^6 。
保证给定的图联通。
#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
const long long oo = 1e18;
int n, m, s, q;
int h[N], to[E], nx[E], wt[E], et;
int vis[N];
long long d[N];
priority_queue <pair<long long, int>> pq;
void ae(int u, int v, int w) {
et++;
to[et] = v;
nx[et] = h[u];
wt[et] = w;
h[u] = et;
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &q);
for (int i = 1; i <= m; i++) {
int u, v, l;
scanf("%d%d%d", &u, &v, &l);
ae(u, v, l);
ae(v, u, l);
}
for (int i = 1; i <= n; i++)
d[i] = oo;
d[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
int u = p.second;
if (vis[u])
continue;
vis[u] = 1;
for (int i = h[u]; i; i = nx[i])
if (d[u] + wt[i] < d[to[i]]) {
d[to[i]] = d[u] + wt[i];
pq.push({-d[to[i]], to[i]});
}
}
while (q--) {
int p;
scanf("%d", &p);
printf("%lld\n", d[p]);
}
return 0;
}割裂
时间限制:1 s,内存限制:512 MB
【问题描述】
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n。
小杨设置了 a 个好点对 {<u1,v1>、<u2,v2>、……、<ua,va>} 和 1 个坏点对 {<bu,bv>}。一个节点能够被删除,当且仅当:
◆ 删除该节点后对于所有的 i(1<=i<=a),好点对 ui 和 vi 仍然连通;
◆ 删除该节点后坏点对 bu 和 bv 不连通。
如果点对中的任意一个节点被删除,其视为不连通。
小杨想知道,有多少个节点能够被删除。
【输入描述】
第一行包含两个正整数 n、a,含义如题面所示。
之后 n - 1 行,每行包含两个正整数 xi、yi,代表存在一条连接节点 xi 和 yi 的边。
之后 a 行,每行包含两个正整数 ui、vi,代表一个好点对 <ui,vi>。
最后一行包含两个正整数 bu、bv,代表坏点对 <bu,bv>。
【输出描述】
输出一个正整数,代表能够删除的节点个数。
【样例输入】
【样例输出】
【数据范围】
对于全部数据,保证有 。

![]()
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, k;
vector<int> e[N];
int f[N][25], dep[N], g[N], h[N];
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for(int i = 1; i <= 20; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for(auto v: e[u]) {
if(v == fa) continue;
dfs(v, u);
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int t = dep[u] - dep[v];
for(int i = 0; i <= 20; i++) {
if(t & (1 << i)) u = f[u][i];
}
for(int i = 20; i >= 0; i--) {
if(f[u][i] != f[v][i])
u = f[u][i], v = f[v][i];
}
if(u == v) return u;
return f[u][0];
}
int ans;
void dfs2(int u, int fa) {
for(auto v: e[u]) {
if(v == fa) continue;
dfs2(v, u);
g[u] += g[v];
h[u] += h[v];
}
if(!g[u] && h[u]) {
ans++;
}
}
void solve() {
cin >> n >> k;
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
for(int i = 1; i <= k; i++) {
int u, v;
cin >> u >> v;
int lc = lca(u, v);
g[u]++, g[v]++, g[lc]--, g[f[lc][0]]--;
}
int u, v;
cin >> u >> v;
int lc = lca(u, v);
h[u]++, h[v]++, h[lc]--, h[f[lc][0]]--;
dfs2(1, 0);
cout << ans << '\n';
}
int main() {
solve();
}树上移动
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n ,每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点 s 和节点 t 并从节点 s 出发移动到节点 t ,移动过程中小杨不能够经过重复节点。
小杨希望自己在至多经过 k 个黑色节点的前提下,经过的总节点数尽可能多,请你帮小杨选择经过最多的节点数是多少。
输入格式
第一行包含两个正整数 n,k,代表节点数量和至多经过的黑色节点数。
第二行包含 n 个正整数 a1,a2,...,an,代表节点颜色,如果 ai=0,代表节点颜色为白色,如果 ai=1,代表节点颜色为黑色。
之后 n−1 行,每行包含两个正整数 ui,vi,代表存在一条连接节点 ui和 vi的边。
输出格式
输出一个正整数,代表最多经过的节点数。
输入样例
输入样例

对于全部数据,保证有 1≤n≤1000,0≤k≤1000,0≤ai≤1。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
vector<int> g[N];
int a[N];
int n,k;
int ans;
void dfs(int x,int fa,int tot,int le){
tot+=a[x];
if(tot>k){
ans = max(ans,le);
return;
}
le++;
ans = max(ans,le);
for(int i:g[x]){
if(i!=fa){
dfs(i,x,tot,le);
}
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++){
dfs(i,0,0,0);
}
cout<<ans<<"\n";
}排队
时间限制:1.0 s
内存限制:512.0 MB
题目描述
小杨所在班级共有 n 位同学,依次以 1,2,...,n 标号。这 n 位同学想排成一行队伍,其中有些同学之间关系非常好,在队伍里需要排在相邻的位置。具体来说,有 m 对这样的关系( m 是一个非负整数)。当 m≥1 时,第 i 对关系 (1≤i≤m) 给出 ai,bi,表示排队时编号为 ai的同学需要排在编号为 bi的同学前面,并且两人在队伍中相邻。
现在小杨想知道总共有多少种排队方式。由于答案可能很大,你只需要求出答案对 109+7 取模的结果。
输入格式
第一行,两个整数 n,m,分别表示同学们的数量与关系数量。
接下来 m 行,每行两个整数 ai,bi,表示一对关系。
输出格式
一行,一个整数,表示答案对 109+7 取模的结果。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
输入样例 3
输出样例 3
数据范围
对于 20% 的测试数据点,保证 1≤n≤8,0≤m≤10 。
对于另外 20% 的测试数据点,保证 1≤n≤103,0≤m≤1 。
对于所有测试数据点,保证 1≤n≤2×105,0≤m≤2×105。
#include <cstdio>
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int pre[N], suf[N];
int vis[N];
int cnt;
int ans;
int main() {
scanf("%d%d", &n, &m);
ans = 1;
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
if (pre[b] == a && suf[a] == b)
continue;
if (pre[b] || suf[a])
ans = 0;
pre[b] = a;
suf[a] = b;
}
for (int i = 1; i <= n; i++) {
if (vis[i])
continue;
int j = i;
while (j) {
if (vis[j] == i)
ans = 0;
if (vis[j])
break;
vis[j] = i;
j = suf[j];
}
}
for (int i = 1; i <= n; i++)
cnt += !pre[i];
for (int i = 1; i <= cnt; i++)
ans = 1ll * ans * i % mod;
printf("%d\n", ans);
return 0;
}