URAL 1962 In Chinese Restaurant 并查集

D - 忠厚人并查集

Source

UESTC 2016 Summer Training #14 Div.2

URAL 1962

My Solution

并查集

以前好像做过类似的题

首先如果一个节点有sz[i] > 2 则 ans = 0

如果有环，而且不是最大的环，则ans = 0

如果是最大的环，则ans = 2 //! 最开始误认为是1，白白WA了2发，然后才明白顺时针和逆时针2种方案

剩下的就是常规的ans了

先是求树的全排列， // 更像是圆排列 A(n, n) / n 或者说把1的位置固定然后求全排列

然后对于每个树：

1）只要节点数大于1，都会有2头无论是不是直链，都和直链一样

因为如果有2个分支，那么那两个分支自己必须是直链(否则 ans = 0)，两个直链拼到root上，拉直就是直链

所以这个时候每个树 ans*2

1)如果该树只有一个节点，则只有一种情况了

复杂度 O(n)

#include 
#include 
#include 

#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

map<int, map<int, int> > cnt;

int father[maxn], _rank[maxn], sz[maxn], trees[maxn];
bool flag;
inline void DisjointSet(int n)
{
    for(int i = 0; i <= n; i++){
        father[i] = i;
        trees[i] = 1;
    }
}

int _find(int v)
{
    return father[v] == v ? v : _find(father[v]);
}

void _merge(int x, int y)
{
    int a = _find(x), b = _find(y);
    if(a == -1 || b == -1) return;                //
    if(_rank[a] < _rank[b]){
        father[a] = b;
        trees[b]++;
    }
    else{
        father[b] = a;
        trees[a]++;
        if(_rank[a] == _rank[b]){
            _rank[a]++;
        }
    }
}


const LL Hash = 1e9 + 7;

inline LL mod(LL x)
{
    return x - x/Hash*Hash;
}


int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    int T = 3;
    while(T--){
    #endif // LOCAL
    memset(sz, 0, sizeof sz);
    int n, m, val, sum;
    LL ans = 1;
    flag = true;
    scanf("%d%d", &n, &m);
    sum = n;
    DisjointSet(n);
    for(int i = 1; i <= m; i++){ scanf("%d", &val); if(cnt[i][val] || cnt[val][i]) continue; sz[i]++; cnt[i][val]++; sz[val]++; cnt[val][i]++; if(sz[i] > 2 || sz[val] > 2) flag = false;
        //if(flag){
            if(_find(val) != _find(i)){
                trees[_find(i)] += trees[_find(val)];
                father[_find(val)] = father[_find(i)];
                sum--;
            }
            else flag = false;
        //}
    }
    if(n == 2) {printf("1"); return 0;}
    for(int i = 1; i <= n; i++){ if(sz[i] > 2) {printf("0"); return 0;}
    }
    if(!flag) {if(sum > 1)printf("0"); else printf("2");}  //!大环是2 不是 1 (┬＿┬)
    else{
        //cout<<"sum"<<sum<<endl;
        for(int i = 1; i < sum; i++)
            ans = mod(ans*i);
        //cout<<ans<<endl;
        for(int i = 1; i <= n; i++){ if(father[i] == i){ if(trees[i] > 1) {ans = mod(ans*2);}

            }
        }
        printf("%I64d", ans);
    }
    #ifdef LOCAL
    cnt.clear();
    printf("n");
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

URAL 1962 In Chinese Restaurant 并查集

相关推荐

Codeforces Round #381 (Div. 2) D. Alyona and a tree dfs+二分+线段树延迟操作、树形化线性

UVALive 6910 Cutting Tree 并查集

Gym – 101173F Free Figurines 思维题+并查集

UESTC 1583 曜酱的心意树状数组求逆序数

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

URAL 1962 In Chinese Restaurant 并查集

相关推荐

Codeforces Round #381 (Div. 2) D. Alyona and a tree dfs+二分+线段树延迟操作、树形化线性

UVALive 6910 Cutting Tree 并查集

Gym – 101173F Free Figurines 思维题+并查集

UESTC 1583 曜酱的心意 树状数组求逆序数

共有 0 条评论

公告

游戏服务器开发最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

UESTC 1583 曜酱的心意树状数组求逆序数