ZOJ 2612. Stable Sets

Brief description :

给定一个模 r 整数环,子集 A 在多项式 p 下被称为是稳定的,当且仅当集合中的数字代入 p 以后的运算结果,刚好也是 A 子集。
题目给定两组多项式 p、q,求同时在 p 和 q 下都稳定的子集的组数。

Analyse :

这个题,不难想象成一个图论问题,考察多项式 p,对于每一组 (i, p(i)),我们连一条 i 到 p(i) 的
有向边,于是求一组极小的稳定集等价于图中的一组强连通分量,如果最后存在 n 个 component,那么最后的结果不难得到是 2^n。

观察图形,发现本题中所有的结点出度都为 1,即由此可以设计出一种简易的方法求取强连通分量的方法,每次找到一个入度为 0 的点,(则此点不可能在一个环结构类)
用一个队列和并查集不断维护即可。另外需要注意的则是需要在 p, q 下保持极小稳定核保持相同,而这种方法则可以方便的将那些已经不可能构成环结构的点丢弃到一个哑类中。(具体此处的实现呢还是有许多值得商讨的地方的。)

/*
    Author: xiaodao
    Prog: ZOJ 2612. Stable Sets
    Status: Accepted
    Last modifiy: GMT +8 Aug. 29th 17:49
*/
#include 
#include 
#include 
#include "bignum.h"
using namespace std;
const int N = 101;
int A[N], n; int P[N];
int r; bignum ans;



int Find(int x){
    if ( P[x] != x ) P[x] = Find(P[x]) ;
    return P[x];
}

void Union(int x,int y){
    x = Find(x); y = Find(y);
    if (x < y) P[x] = y ; // # 
    else P[y] = x;
}


int p(int x){
    int res = 0;
    for (int i=n;i>=0;i--)
        res = ((res * x) + A[i]) % r;
    return res;
}

void input(){
    scanf("%d", &n);
    for (int i=n;i>=0;i--)
        scanf("%d", &A[i]);

    int in[N];
    memset(in, 0, sizeof(in));
    for (int i=0;i> r && r>0){
        init(); input(); input(); stat();
        cout << ans << endl;
    }
}