In Chinese Restaurant
题目连接：
http://acm.hust.edu.cn/vjudge/contest/123332#problem/B
Description
When Vova arrived in Guangzhou, his Chinese friends immediately invited him to a restaurant. Overall n people came to the restaurant, including Vova. The waiter offered to seat the whole company at a traditional large round table with a rotating dish plate in the center.
As Vova was a guest, he got the honorable place by the door. Then m people in the company stated that they wanted to sit near a certain person. Your task is to determine the number of available arrangements to seat Vova's friends at the table.
Input
The first line contains integers n and m (2 ≤ n ≤ 100; 0 ≤ m ≤ n). The next m lines contain integers k1, …, km, where ki is the number of the person who the person number i wants to sit with (1 ≤ ki ≤ n; ki ≠ i). Being an honorable guest, Vova got number 1. His friends are numbered with integers from 2 to n.
Output
Print the number of available arrangements to seat Vova's friends modulo 10 9 + 7.
Sample Input
6 6
2
1
1
5
6
5
Sample Output
4
Hint
题意
有n个人在坐在一个圆桌上，给你m个关系a,b,表示a要挨着b坐
问你有多少个方案数
题解：
如果出现环，答案为2，否则就是全排列乘以2
特判掉 只有两个人的情况，因为这样正着坐和反着坐答案是一样的。
代码
#include <bits/stdc++.h>
#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define pb push_back
#define mp make_pair
#define sf scanf
#define pf printf
#define two(x) (1<<(x))
#define clr(x,y) memset((x),(y),sizeof((x)))
#define dbg(x) cout << #x << "=" << x << endl;
const int mod = 1e9 + 7;
int mul(int x,int y){return 1LL*x*y%mod;}
int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
using namespace std;
const int maxn = 1e3 + 15;
vector<int>G[maxn],block[maxn];
int n , m ,vis[maxn] , c[maxn],tot,sz[maxn],deg[maxn],fac[maxn],C[maxn][maxn],moo[maxn][maxn];
set < int > Edge[maxn];
void maintain(int & x){
if( x >= mod ) x-= mod;
}
bool dfs1( int x , int pre ){
c[x] = 1;
for(auto v:G[x]){
if( v == pre ) continue;
if(c[v] == 1) return true;
else if(c[v] == 0){
if(dfs1(v,x)) return true;
}
}
c[x] = 2;
return false;
}
void predfs( int x ){
block[tot].pb( x );
for(auto v : G[x])
if( vis[v] == 0 ){
vis[v] = 1;
predfs( v );
}
}
void init(){
fac[0] = 1;
C[0][0] = 1;
rep(i,1,maxn-1){
fac[i] = mul( fac[i - 1] , i );
C[i][0] = 1;
rep(j,1,i){
C[i][j] = C[i][j - 1] + C[i - 1][j - 1] ;
maintain( C[i][j] );
}
}
}
int main(int argc,char *argv[]){
init();
n=read(),m=read();
if(n == 2 && m >= 1 ){
pf("1\n");
return 0;
}
rep(i,1,n) G[i].clear();
rep(i,1,m){
int v=read();
Edge[i].insert( v );
moo[i][v]=moo[v][i]=1;
}
rep(i,1,n){
rep(j,1,n) if( moo[i][j] && i != j ) G[i].pb( j );
}
int ok = 0;
rep(i,1,n) if(c[i] == 0){
if( dfs1( i , 0 ) ){
ok = 1;
break;
}
}
rep(i,1,n) if(!vis[i]){
vis[i]=1;
++ tot;
predfs( i );
}
// 有三条边或以上
rep(i,1,n){
int kk = 0;
rep(j,1,n) if( moo[i][j]) ++ kk;
if( kk > 2 ){
pf("0\n");
return 0;
}
}
if( ok ){
if( tot == 1 ){
int judge = 1;
rep(i,1,n) if(c[i] != 1) judge = 0;
if( judge == 1 ) pf("%d\n" , 2);
else pf("0\n");
}else pf("0\n");
return 0;
}else{
int ptr = 0 ;
rep(i,1,tot){
for(auto it : block[i]){
if( it == 1 ){
ptr = i;
}
}
}
int ans = 1 ;
if( block[ptr].size() > 1 ) ans = 2;
rep(i,1,tot){
if( i == ptr ) continue;
int cap = block[i].size();
if( cap > 1 ) ans = mul( ans , 2 );
}
ans = mul( ans , fac[ tot - 1 ] );
pf("%d\n" , ans );
}
return 0;
}