企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P11380 [GESP202412 八级] 排队

【题目描述】

小杨所在班级共有n nn位同学，依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n标号。这n nn位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有m mm对这样的关系（m mm是一个非负整数）。当m ≥ 1 m\geq 1m≥1时，第i ii对关系（1 ≤ i ≤ m 1\leq i\leq m1≤i≤m）给出a i , b i a_i,b_iai​,bi​，表示排队时编号为a i a_iai​的同学需要排在编号为b i b_ibi​的同学前面，并且两人在队伍中相邻。

现在小杨想知道总共有多少种排队方式。由于答案可能很大，你只需要求出答案对10 9 + 7 10^9+7109+7取模的结果。

【输入】

第一行，两个整数n , m n,mn,m，分别表示同学们的数量与关系数量。

接下来m mm行，每行两个整数a i , b i a_i,b_iai​,bi​，表示一对关系。

【输出】

一行，一个整数，表示答案对10 9 + 7 10^9+7109+7取模的结果。

【输入样例】

4 2 1 3 2 4

【输出样例】

2

【核心思想】

1. 问题分析：n nn位同学排成一行，m mm对关系要求a i a_iai​排在b i b_ibi​前面且相邻。求合法排队方案数对10 9 + 7 10^9+7109+7取模。本质是链表构建 + 排列组合问题，核心在于将相邻约束转化为链表结构，再计算链的排列数。

2. 算法选择：

   • 链表构建 + 环检测：用l[]和r[]数组记录每个节点的左右邻居，构建若干条链
   • 阶乘计算排列数：若有c n t cntcnt条互不干扰的链，则方案数为c n t ! cnt!cnt!

3. 关键步骤：

   • 读入数据：n nn、m mm，以及m mm对关系( a i , b i ) (a_i, b_i)(ai​,bi​)
   • 构建链表并检测矛盾：
     • 若l [ b ] ≠ 0 l[b] \neq 0l[b]=0且l [ b ] ≠ a l[b] \neq al[b]=a（b bb左边已有其他人），或r [ a ] ≠ 0 r[a] \neq 0r[a]=0且r [ a ] ≠ b r[a] \neq br[a]=b（a aa右边已有其他人），输出0 00
     • 否则：l [ b ] = a l[b] = al[b]=a，r [ a ] = b r[a] = br[a]=b
   • DFS 遍历链并检测环：
     • 对每个链头（l [ i ] = 0 l[i] = 0l[i]=0）开始 DFS，统计访问节点数n u m numnum
     • 若访问到已访问节点，说明有环，输出0 00
   • 验证完整性：若n u m ≠ n num \neq nnum=n，说明有孤立节点无法排入链，输出0 00
   • 计算答案：a n s = c n t ! m o d ( 10 9 + 7 ) ans = cnt! \bmod (10^9+7)ans=cnt!mod(109+7)，其中c n t cntcnt为链的数量

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，构建链表O ( m ) O(m)O(m)，DFS 遍历O ( n ) O(n)O(n)，阶乘计算O ( c n t ) ≤ O ( n ) O(cnt) \leq O(n)O(cnt)≤O(n)
   • 空间复杂度：O ( n ) O(n)O(n)，链表数组和访问标记

5. 链表构建与排列组合的核心思想：

   • 相邻约束的链表化：每对关系a → b a \to ba→b表示a aa和b bb必须相邻且a aa在左。多个关系可能连接成链（如1 → 3 → 5 1 \to 3 \to 51→3→5），链内顺序固定，链间可任意排列
   • 矛盾检测的完备性：一个节点最多有一个左邻居和一个右邻居，违反此约束即存在矛盾（如a → b a \to ba→b且c → b c \to bc→b）。同时检测环（如1 → 2 → 1 1 \to 2 \to 11→2→1）和孤立节点
   • 链的排列独立性：每条链作为一个整体参与排列，c n t cntcnt条链的全排列数为c n t ! cnt!cnt!。链内部顺序已由约束唯一确定，无需额外计算
   • DFS 的环检测：从链头出发沿r[]指针遍历，若遇到已访问节点则说明存在环（矛盾关系），立即输出0 00
   • 适用于相邻约束排列、链表构建、环检测类问题

【算法标签】

#普及 #排列组合

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int宏定义为long long，防止阶乘计算溢出constintN=200005,mod=1e9+7;// N为最大节点数常量，mod为取模数1e9+7intn,m,num;// n为同学数量，m为关系数量，num为DFS已访问的节点数intl[N],r[N];// l[u]表示u左边的同学编号，r[u]表示u右边的同学编号（构建链表关系）boolvis[N];// vis[u]标记节点u是否已被访问（用于检测环）voiddfs(intu)// 深度优先搜索，从链头u开始遍历整条链，统计链长度并检测是否有环{if(vis[u])// 如果u已经被访问过，说明存在环（矛盾关系）{cout<<0<<endl;// 输出0表示不存在合法排队方案exit(0);// 直接退出程序}num++;// 已访问节点数加1vis[u]=1;// 标记u已访问if(r[u]!=0)// 如果u有右边的相邻同学dfs(r[u]);// 递归访问右边的同学，继续遍历链条}signedmain()// 使用signed main是因为#define int long long后，main返回值类型需要显式声明{cin>>n>>m;// 读入同学数量n和关系数量mfor(inti=1;i<=m;i++)// 循环读入m对相邻关系{inta,b;cin>>a>>b;// 读入一对关系：a需要排在b前面且相邻（a在b左边）// 检查关系是否矛盾：// 1. b已经有左边的人l[b]，且不是a（b左边只能有一个人）// 2. a已经有右边的人r[a]，且不是b（a右边只能有一个人）if(l[b]!=0&&l[b]!=a||r[a]!=0&&r[a]!=b){cout<<0<<endl;// 关系矛盾，不存在合法方案return0;// 直接结束程序}l[b]=a;// 记录b的左边是ar[a]=b;// 记录a的右边是b}intcnt=0;// cnt记录链条的数量（每个链头对应一条链）for(inti=1;i<=n;i++)// 遍历所有同学，寻找链头（左边没有人的同学）{if(l[i]==0)// 如果i的左边没有人，说明i是一条链的链头{cnt++;// 链条数量加1dfs(i);// 从链头i开始DFS遍历整条链}}if(num!=n)// 如果DFS访问的节点数不等于n，说明有节点不在任何链中（孤立点或矛盾）{cout<<0<<endl;// 存在无法排入链的节点，不存在合法方案return0;// 直接结束程序}intans=1;// ans为最终答案，初始化为1for(inti=1;i<=cnt;i++)// 计算cnt条链的全排列数ans=ans*i%mod;// ans = cnt! % mod，即cnt条链可以有cnt!种排列方式cout<<ans<<endl;// 输出合法排队方案数对1e9+7取模的结果return0;}

【运行结果】

4 2 1 3 2 4 2