BZOJ 3444: 最后的晚餐( )

把暗恋关系看成无向边, 那某个点度数超过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

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

HINT

Source

By lll6924 at“酱油杯noi考后欢乐赛”

巴特西