提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

【MemSQL Start[c]UP 3.0 - Round 1 E】Desk Disorder

round 3.0 start Up
2023-09-14 09:03:49 时间

【链接】h在这里写链接


【题意】


有N个人。
2N个座位。
现在告诉你这N个人它们现在的座位。以及它们想去的座位。
每个人可以去它们想去的座位或者就站在原地不动。
新的座位和旧的座位,都不允许一个座位被两个人占据的情况。
问你安排的方案数。

【题解】


这是一个n个节点,n条边的图。
构成的图有两种情况。
->各个连通块独立计算答案,然后乘起来。
如果n个点,n-1条边。
则是一棵树。
那么写个例子就会发现,答案就是节点的个数。

如果n个点,那条边

会出现一个环(且恰好只有一个环);

如果是一个自环。那么答案为1.

因为所有人都不能动。->动了的话,那个自环上的人是无法走的。

如果这个环的长度大于等于2.

则答案为2.

因为除了环上的人,其他人都不能动。

且环上的人要么全动，要么全不动。

两种情况。

可以用并查集来判断有没有出现环。

如果是自环的话,答案直接设置为1就好。

如果没有环。

则答案为并查集的大小(找f(i)==i的根节点);

如果有环

答案就为2.

(各个连通块答案累乘就好)



【错的次数】


2

【反思】


tarjan不知道哪里写错了>_<
下次一个环的这种题就别写tarjan了。
并查集找环很方便啊!

【代码】

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5;
const long long MOD = 1e9+7;

int n,f[N+10],cycle[N+10],size[N+10];

int ff(int x){ if (f[x]==x) return x;else return f[x] = ff(f[x]);}

int main(){
    //freopen("F:\\rush.txt","r",stdin);
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for (int i = 1;i <= 2*n;i++) f[i] = i,size[i]=1;
    for (int i = 1,x,y;i <= n;i++){
        cin >> x >> y;
        if (x==y){
            cycle[ff(x)]=2;
            continue;
        }
        int r1 = ff(x),r2 = ff(y);
        if (r1!=r2){
            f[r2] = r1;
            size[r1]+=size[r2];
            cycle[r1]|=cycle[r2];
        }else
            cycle[r1] = 1;
    }
    long long ans = 1;
    for (int i = 1;i <= 2*n;i++)
        if (ff(i)==i){
            if (cycle[i]==1)
                ans = ans*2%MOD;
            else
                if (cycle[i]==0)
                    ans = ans*size[i]%MOD;
        }
    cout << ans << endl;
    return 0;
}


相关文章