URAL1962:In Chinese Restaurant(并查集)

Open Ural FU Personal Contest 2013

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  k 1, …,  k m, where  k i is the number of the person who the person number  i wants to sit with (1 ≤  k i ≤  n;  k i ≠  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.

Samples

input	output
6 6 2 1 1 5 6 5	4
4 3 2 3 1

題意：有n個人，分别編号1~n，有m個人分别表達自己的意願，這m個人分别是1~m編号的這幾個人

然後給出m個數，表示第i個人想要坐在第x個人的旁邊，現在要求的是，在滿足了這m個人的意願的情況下，這張大圓桌有幾種坐法

思路：我們首先來分析，對于那些想要坐在臨近的人必然是互相相連的，那麼他們就可以構成一棵樹，那麼對于總共的坐法，就是對s棵樹的全排列

對于單個點的樹，我們可以不用太多考慮

那麼對于有子節點的樹，我們要考慮環的問題

如果成環了，那麼必然隻剩這棵樹本身，如果還有其他子樹，那麼必然無法滿足

對于不成環的情況，我們還要注意的是對于單個節點，如果其身邊必須安排的人數大于2，那麼是無法滿足的，因為他身邊最多隻能安排2個人

那麼對于每棵樹，這棵樹不隻一個節點，那麼必然有兩種情況

首先，如果是一條直鍊，例如1-2，我們有1-2和2-1兩種

對于不是直鍊，那麼肯定可以交換左右兩支

什麼？你說三鍊？這種情況之前就否定了，是0

解決了這些問題之後，這道題就解決了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define up(i,x,y) for(i=x;i<=y;i++)
#define down(i,x,y) for(i=x;i>=y;i--)
#define mem(a,x) memset(a,x,sizeof(a))
#define w(a) while(a)
#define LL long long
const double pi = acos(-1.0);
#define Len 200005
#define mod 1000000007
const int INF = 0x3f3f3f3f;

int vis[105][105];
int father[105];
int d[105],s[105];
LL ans;

int find(int x)
{
    if(father[x]==x) return x;
    return father[x] = find(father[x]);
}

int main()
{
    int n,m,i,j,k,x;
    w(~scanf("%d%d",&n,&m))
    {
        mem(vis,0);
        up(i,0,n)
        {
            father[i] = i;
            s[i] = 1;//這棵樹的節點的情況
            d[i] = 0;//d[i]是i的周圍必須安排幾個人
        }
        int sum = n,flag = 0;
        up(i,1,m)
        {
            scanf("%d",&x);
            if(vis[i][x] || vis[x][i]) continue;
            vis[i][x] = vis[x][i] = 1;
            d[i]++;
            d[x]++;
            if(find(x)!=find(i))
            {
                s[find(i)]+=s[find(x)];
                father[find(x)] = father[find(i)];
                sum--;//減少了一棵樹
            }
            else
                flag = 1;//成環
        }
        if(n==2)//隻有兩個人必然隻有一種坐法
        {
            printf("1\n",ans);
            continue;
        }
        up(i,1,n)
        {
            if(d[i]>2)//i的旁邊要安排的人數大于2，必然無法滿足
                break;
        }
        if(i<=n || (sum>1&&flag))//成環并且除了這棵子樹還有其他子樹，必然無法滿足
        {
            printf("0\n");
            continue;
        }
        ans = 1;
        up(i,1,sum-1)//對于這些樹全排列的方式有幾種，但是1的位置是固定的
        ans = (ans*i)%mod;
        up(i,1,n)
        {
            if(father[i]==i && s[i]>1)//看根節點，如果這棵樹不隻一個節點，那麼就有兩種情況
                ans = (ans*2)%mod;
        }
        printf("%I64d\n",ans);
    }

    return 0;
}