Breaking Into Atoms (ATOMS)

keyword

集合　C++

問題概要

0~N-1(N<100)を要素に持つ集合がM(<30)個ある。全ての集合を部分集合族A_iで被覆する。A_iの要素は全てS_jに含まれるか全てS_jに含まれていないかのどちらかである。最小いくつで被覆できるか求める問題。

解法

0~N-1から2つ選んで同じかどうかUnion Findで管理する。計算量O(N^2 * M) (実際の実装はsetで手抜きしている分log Nがかかる)。各要素がどのS_jに含まれるかで管理する方法もあって、これだと計算量O(N*M)。

int pars[102];
bool visited[102];
int getRoot(int x){ return x==pars[x]?x:(pars[x]=getRoot(pars[x])); }
bool isSame(int x,int y){ return getRoot(x)==getRoot(y); }
void merge(int x,int y){ pars[getRoot(x)] = getRoot(y); }

set<int> S[33];
int N, M;

int solve(){
    for(int i=0; i<N; i++) pars[i]=i;
    for(int i=0; i<N; i++) visited[i] = false;
    for(int i=0; i<M; i++){
        EACH(S[i],it) visited[*it] = true;
    }
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            bool same = true;
            for(int k=0;k<M;k++){
                if((S[k].find(i)==S[k].end()) ^ (S[k].find(j)==S[k].end())) same=false;
            }
            if(same) merge(i,j);
        }
    }
    int ans = 0;
    for(int i=0; i<N; i++)if(visited[i]){
        if(getRoot(i)==i) ans++;
    }
    return ans;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        for(int i=0; i<M; i++)S[i].clear();
        for(int i=0; i<M; i++){
            int k;
            scanf("%d",&k);
            for(int j=0; j<k; j++){
                int x;
                scanf("%d",&x);
                S[i].insert(x);
            }
        }
        printf("%d\n",solve());
    }
    return 0;
}