把暗恋关系看成无向边, 那某个点度数超过2就无解。存在环也是无解。有解的话对连通分量进行排列就行了。

----------------------------------------------------------------------------------

#include<cstdio>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 500009;
const int MOD = 989381;
 
pair<int, int> e[maxn << 1];
int N, cnt[maxn], Vn = -1, en = 0, deg[maxn];
bool vis[maxn];
 
struct edge {
int to;
edge* next;
} E[maxn << 1], *pt = E, *head[maxn];
 
void AddEdge(int u, int v) {
deg[pt->to = v]++; pt->next = head[u]; head[u] = pt++;
}
 
void Init() {
memset(vis, 0, sizeof vis);
memset(deg, 0, sizeof deg);
memset(cnt, 0, sizeof cnt);
int m;
scanf("%d%d", &N, &m);
while(m--) {
int u, v;
scanf("%d%d", &u, &v); u--; v--;
e[en++] = make_pair(u, v);
e[en++] = make_pair(v, u);
}
sort(e, e + en);
en = unique(e, e + en) - e;
for(int i = 0; i < en; i++)
AddEdge(e[i].first, e[i].second);
}
 
bool Check() {
for(int i = 0; i < N; i++)
if(deg[i] > 2) return false;
return true;
}
 
bool Dfs(int x, int p) {
if(vis[x]) return true;
vis[x] = true;
cnt[Vn]++;
for(edge* e = head[x]; e; e = e->next)
if(e->to != p && Dfs(e->to, x)) return true;
return false;
}
 
int main() {
Init();
if(!Check()) {
puts("0"); return 0;
}
for(int i = 0; i < N; i++) if(!vis[i]) {
Vn++;
if(Dfs(i, -1)) {
puts("0"); return 0;
}
}
Vn++;
int ans = 1;
for(int i = 2; i <= Vn; i++)
ans = ll(i) * ans % MOD;
for(int i = 0; i < Vn; i++)
if(cnt[i] > 1 && (ans <<= 1) >= MOD) ans -= MOD;
printf("%d\n", ans);
return 0;
}

----------------------------------------------------------------------------------

3444: 最后的晚餐

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 342  Solved: 128
[Submit][Status][Discuss]

Description

【问题背景】
高三的学长们就要离开学校,各奔东西了。某班n人在举行最后的离别晚餐时,饭店老板觉得十分纠结。因为有m名学生偷偷找他,要求和自己暗恋的同学坐在一起。
【问题描述】
饭店给这些同学提供了一个很长的桌子,除了两头的同学,每一个同学都与两个同学相邻(即坐成一排)。给出所有信息,满足所有人的要求,求安排的方案总数(这个数字可能很大,请输出方案总数取余989381的值,也可能为0)。

Input

输入有m+1行,第一行有两个用空格隔开的正整数n、m,如题所示。接下来的m行,每一行有两个用空格隔开的正整数,第i行为Ai和Bi,表示Ai的暗恋对象为Bi,保证Ai互不相等。

Output

输出只有一行,这一行只有一个数字,如题所示。

Sample Input

4 2
1 2
4 3

Sample Output

8

【数据范围】
100%的数据,0<n≤500000,1≤Ai,Bi≤n,0≤m≤n,保证没有人自恋。

HINT

Source

最新文章

  1. GroupData群数据库的还原与优化
  2. 【FLUENT案例】04:利用DDPM+DEM模拟鼓泡流化床
  3. HUAS_ACM 个人训练#2 C
  4. 浏览器加载和渲染html的顺序
  5. System.BadImageFormatException: Could not load file or assembly
  6. [译]git log
  7. Python 资源
  8. jQuery UI的基本使用方法与技巧
  9. poj2392 Space Elevator(多重背包)
  10. 更好列表页中一个航班.先unset删除数组中一个键值对,再追加,最后按键排序
  11. JavaEE开发之Spring中的事件发送与监听以及使用@Profile进行环境切换
  12. Dynamics Business Central-如何配置VS Code连接BC环境
  13. Ubuntu系统桌面任务栏和启动器全部消失解决方案
  14. HTML5中的input type为file控件限制上传文件类型及扩展
  15. 【洛谷P2860】冗余路径
  16. hotmail 收不到邮件的问题
  17. springboot面试题总结
  18. CentOS 使用 Docker 安装 Sentry
  19. $Simpson$积分入门
  20. struts2框架值栈的概述之问题一:什么是值栈?

热门文章

  1. 写个脚本列出neutron的ovs的topology。
  2. 将外部准备好的sqlite导入到项目当中
  3. Android学习路线(六)为Android应用加入ActionBar
  4. 【DateStructure】 Charnming usages of Map collection in Java
  5. SQL学习之计算字段的用法与解析
  6. Python 读写文件操作
  7. matlab最小二乘法数据拟合函数详解
  8. FlashFXP使用教程
  9. ios本地文件内容读取,.json .plist 文件读写
  10. Java学习之网络编程