把暗恋关系看成无向边, 那某个点度数超过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. Spring5:@Autowired注解、@Resource注解和@Service注解
  2. POMDP
  3. IOS 解析crashlog
  4. Java里正则表达式
  5. {POJ}{树状数组}
  6. Installing Oracle and ArcSDE on separate servers
  7. java jmx
  8. jdk集合常用方法分析之ArrayList&amp;LinkedList&amp;以及两者的对比分析
  9. HDU 1796How many integers can you find(简单容斥定理)
  10. [Linux]关机和重启命令
  11. phpcms:五、网站首页(index.html)
  12. hdu 4463 Outlets(最小生成树)
  13. 求链表内环的入口节点-Java
  14. P1313 计算系数
  15. 解码escape类型的unicode
  16. [PHP] 算法-将一个字符串转换成一个整数的PHP实现
  17. python 爬虫启航2.0
  18. Eclipse集成Gradle 【Eclipse在线安装Gradle插件方法】
  19. day3_字典
  20. 20155311高梓云《网络对抗》逆向及Bof基础

热门文章

  1. 发布MFC ActiveX控件并实现自动更新
  2. flash跨域策略文件crossdomain.xml
  3. uber在限制新司机加入了,看看新政策把
  4. MFC知识点整理
  5. Node.cloneNode()方法
  6. Ubuntu常用命令整理
  7. android 文件操作类简易总结
  8. poj2987 Firing
  9. 并发编程:c++11 多线程中随机数重复问题
  10. ThinkPHP第二十一天(JQuery元素获取,parents属性,toggle方法,确认弹出对话框使用)