并查集排列组合 In Chinese Restaurant:URAL - 1962

向右看齐 2022-06-13 04:58 142阅读 0赞

## 题目:[In Chinese Restaurant:URAL - 1962][In Chinese Restaurant_URAL - 1962] ##

## 题意: ##

有N个人要坐在一张圆桌上，给出M对关系K\[1..M\]，表示第i个人想坐在k\[i\]边上。问存在多少种不同的分配方案，结果模1e9+7。1号玩家位置固定.

## 思路: ##

统计每个人的入度，如果有人入度大于2则无解。利用并查集将想坐在一起的人合并起来，个数记为sn，以及集合人数大于1的个数c，同时要小心可能存在环。如果sn>1并且存在环的话无解。如果N=2则解为1。其他情况下，答案为(sn−1)!∗2c

## 代码: ##

#include<iostream>
    #include<cstdio>
    #define int long long
    using namespace std;
    const int INF=1e9+7;
    int d[300],f[300],sz[300],b[300][300];
    int sf(int d){
       return f[d]==d? d:f[d]=sf(f[d]);}
    main(){
        bool flag=0,ok=0;
        int n,m,num,ans=1,x;cin >>n>>m;num=n;
        if (n==2) return puts("1");
        for (int i=1;i<=n;++i) f[i]=i;
        for (int i=1;i<=n;++i) sz[i]=1;
        for (int i=1;i<=m;++i){
            cin >>x;int fx=sf(i),fy=sf(x);
            if (b[x][i]||b[i][x]) continue;
            ++d[x];++d[i];b[i][x]=b[x][i]=1;
            if (fx!=fy){
                num--;
                f[fx]=fy;sz[fy]++;sz[fx]=0;
            }else ok=1;
        }
        for (int i=1;i<=n;++i) if (d[i]>2) flag=1;
        if (flag||ok&&num>1) return puts("0");
        for (int i=1;i<num;++i) ans=(ans*i)%INF;
        for (int i=1;i<=n;++i) if (sz[i]>1) ans=(ans*2)%INF;
        cout <<ans<<endl;return 0;
    }

[In Chinese Restaurant_URAL - 1962]: http://acm.timus.ru/problem.aspx?space=1&num=1962

发表评论取消回复

表情：

评论列表（有 0 条评论，142人围观）

还没有评论，来说两句吧...

相关阅读

相关【并查集+组合计数】ABC226 E

[E - Just one (atcoder.jp)][E - Just one _atcoder.jp] 题意： ![06f50f3c719f4819a171a6d800

￡神魔★判官ぃ/ 2024年03月17日 19:11/ 0 赞/ 118 阅读

相关并查集

并查集JAVA版框架并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作： \--查询元素a和元素b是否属于同一组

落日映苍穹つ/ 2022年06月16日 12:44/ 0 赞/ 385 阅读

相关并查集

这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 372 阅读

相关并查集排列组合 In Chinese Restaurant:URAL - 1962

题目:[In Chinese Restaurant:URAL - 1962][In Chinese Restaurant_URAL - 1962] 题意: 有N个人

向右看齐/ 2022年06月13日 04:58/ 0 赞/ 143 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 400 阅读

相关 (PAT 1118) Birds in Forest (并查集)

Some scientists took pictures of thousands of birds in a forest. Assume that all the bir

深藏阁楼爱情的钟/ 2022年04月23日 09:12/ 0 赞/ 221 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 470 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 466 阅读

相关求全排列和非空子集算法——排列组合

在数学种排列和组合都是很重要的，在算法中也是，下面我们将介绍几种求全排列和求元素所有子集的方法。一、全排列全排列如果使用递归来实现的话是元素与元素交换的问题，而如果使用

野性酷女/ 2021年09月28日 19:44/ 0 赞/ 459 阅读

相关并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并基本模板 include <iostream> include <a

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 671 阅读