一、并查集

1.1 并查集简介

并查集是一种简单的集合表示，是一种树形数据结构，可处理不相交集合的合并及查询问题。并查集可求联动分支数。

并查集存储：

现有9个元素0~9，建立一个数组（初始化元素为-1），用数组下标表示元素，数组中的数据表示根节点的下标。数组中数据为负数时表示它是根节点。

并查集支持以下3种操作：

Initial(S)：将集合S中每个元素都初始化为只有一个单元素的子集合。
Union(S,Root1,Root2)：把集合S中的子集合Root2并入子集合Root1.要求Root1和Root2互不相交，否则不执行合并。
Find(S,x)：查找集合S中单元素x所在的子集合，并返回该子集合的根节点。

2.2 并查集实现

#define SIZE 100
int UFSets[SIZE];//集合元素数组
//Initial操作
void Initial(int S[])
{
    for(int i=0;i<SIZE;i++)
        s[i]=-1;
}
//Find操作
int Find(int S[],int x)
{
    while(S[x]>=0)//寻找x的根结点
        x=S[x];
    return x;
}
//Union操作
void Union(int S[],int Root1,int Root2)
{
    if(Root1==Root2)//要求Root1和Root2是不同的集合
        return;
    S[Root2]=Root1;//将根Root2连接到另一根Root1下面
}

二、题解（LevOJ P1648 炼丹术）

注意：这里根节点元素值是它自身下标，不是-1

/*
P1648 炼丹术
====关键词===================================================
1.暴力：求幂集，判断是否符合标准，计数
2.单方和其稳定剂构成有向图,（由于输入是全排列，故图必然由若干个环组成）,找图中有几个环,再求（幂集数-1）（去掉空集）
    2.1 第一次没过，因为要在mypow中对结果取模（不用开longlong），而非最后对ans取模（过不了）
3.模板：并查集（根节点元素值是它自身下标，不是-1）
====关键词===================================================
====题目===================================================
题目描述
三水最近在学习炼丹术。但是众所周知炼丹术是一门危险的学科，需要大量的调参才能保证安全。好在三水在洗衣机里面找到了一张失传已久的图纸，里面记录了若干种材料的药性。这张图纸上记录了n 种不同的药材，对于每种药材，都需要恰好一种药材来使其稳定 (这种药材可能是其自身，即这种药材本身就很稳定)。三水想知道，通过这张图纸，可以得到多少种不同的稳定的丹方。保证每种药材只会作为稳定剂出现一次。
我们认为一个丹方是从n 种药材中选择若干种 (不为0 )，两个丹方被认为是不同的当且仅当存在一种药材在其中一个丹方中且不在另一个中。我们称一个丹方是稳定的，当且仅当所有出现在丹方中的药材的稳定剂也在药材中。
因为输出结果可能很大，所以答案对 998244353 取模。
输入描述
第一行一个数字n ， 表示有n(1⩽n⩽10^6) 种不同的药材。 接下来一行n 个数字，第i 数字ai(1⩽ai⩽n) 表示药材i 的稳定剂是ai，保证输入是1 到n 的一个全排列。
输出描述
一个整数
n ，表示答案对 998244353 取模的结果。
样例输入
Copy to Clipboard
6
2 3 4 5 6 1
样例输出
Copy to Clipboard
1
====题目===================================================
*/
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e6 + 10;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
int n;      //几个结点
int a[N];   //结点稳定剂
int pre[N]; //并查集
int cnt;    //环数
int ans;    //结果
int mypow(int x)
{ // 求2的x次方（由于取了模，不需要开longlong）
    int ret = 1;
    while (x--)
    {
        ret = (ret * 2) % MOD; //结果取模
    }
    return ret;
}
int find(int x)
{ //寻找x的根节点(若该结点已经是根节点，则返回他自身)
    while (x != pre[x])
    {
        x = pre[x] = pre[pre[x]]; //路径压缩
        // x=pre[x];//不路径压缩
    }
    return x;
}
void show_pre()
{
    cout << "pre ";
    for (int i = 1; i <= n; i++)
    {
        cout << pre[i] << " ";
    }
    cout << endl;
}
int main()
{
    //读数
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        pre[i] = i; //初始化查数组
    }
    //题解
    // show_pre();
    for (int i = 1; i <= n; i++)
    {
        int u = find(i), v = find(a[i]); //通过前缀数组更新并查集，查询过程进行路径压缩
        // printf("u=%d,v=%d\n", u, v);
        if (u != v)
        {
            // printf("pre[%d]=%d\n", u, v);
            pre[u] = v; //合并关联的集合
        }
    }
    // show_pre();
    // find(1);
    // show_pre();
    for (int i = 1; i <= n; ++i)
    { //记录不同集合个数
        if (pre[i] == i)
            cnt++;
    }
    //输出答案
    printf("%d", mypow(cnt) - 1);
    return 0;
}

三、自己写的暴力题解（可对比下）

/*
P1648 炼丹术
====关键词===================================================
1.暴力：求幂集，判断是否符合标准，计数
2.单方和其稳定剂构成有向图,（由于输入是全排列，故图必然由若干个环组成）,找图中有几个环,再求（幂集数-1）（去掉空集）
    2.1 第一次没过，因为要在mypow中对结果取模（不用开longlong），而非最后对ans取模（过不了）
3.模板：并查集
====关键词===================================================
====题目===================================================
题目描述
三水最近在学习炼丹术。但是众所周知炼丹术是一门危险的学科，需要大量的调参才能保证安全。好在三水在洗衣机里面找到了一张失传已久的图纸，里面记录了若干种材料的药性。这张图纸上记录了n 种不同的药材，对于每种药材，都需要恰好一种药材来使其稳定 (这种药材可能是其自身，即这种药材本身就很稳定)。三水想知道，通过这张图纸，可以得到多少种不同的稳定的丹方。保证每种药材只会作为稳定剂出现一次。
我们认为一个丹方是从n 种药材中选择若干种 (不为0 )，两个丹方被认为是不同的当且仅当存在一种药材在其中一个丹方中且不在另一个中。我们称一个丹方是稳定的，当且仅当所有出现在丹方中的药材的稳定剂也在药材中。
因为输出结果可能很大，所以答案对 998244353 取模。
输入描述
第一行一个数字n ， 表示有n(1⩽n⩽10^6) 种不同的药材。 接下来一行n 个数字，第i 数字ai(1⩽ai⩽n) 表示药材i 的稳定剂是ai，保证输入是1 到n 的一个全排列。
输出描述
一个整数
n ，表示答案对 998244353 取模的结果。
样例输入
Copy to Clipboard
6
2 3 4 5 6 1
样例输出
Copy to Clipboard
1
====题目===================================================
*/
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e6 + 10;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
int n;           //几个结点
int a[N];        //结点稳定剂
bool visited[N]; //结点是否被访问
int ring;        //环数
int ans;         //结果
int mypow(int x)
{ // 求2的x次方（由于取了模，不需要开longlong）
    int ret = 1;
    while (x--)
    {
        ret = (ret * 2) % MOD; //结果取模
    }
    return ret;
}
void find_ring()
{
    int ss, s, e;
    //从第一个结点开始
    for (int i = 1; i <= n; i++)
    {
        if (!visited[i])
        {
            ring++; //环数+1
            ss = i;
            s = i;
            e = a[s];
            visited[i] = true;
            while (ss != e)
            { //将处于同一个环的结点都标记上
                s = e;
                e = a[s];
                visited[s] = true;
            }
        }
    }
}
int main()
{
    //读数
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    //题解
    find_ring();
    ans = mypow(ring) - 1;
    //输出答案
    printf("%d", ans);
    return 0;
}