2524:Ubiquitous Religions

keyword

Union-Find　C++

概要

学生がN(<50000)人いる。各学生は何らか一つの宗教に属している。ある学生とある学生が同じ宗教に属しているという情報が複数与えられる。学生が所属している宗教は最大で何種類あるかを求める問題。
union-findするだけ。

int main(){
    int n, m, cnt = 1;
    while(n = readint(), m = readint(), n){
        for(int i=1; i<=n; i++) pars[i] = i;
        for(int i=0; i<m; i++){
            merge(readint(), readint());
        }
        int ans=0;
        for(int i=1; i<=n; i++)if(i==getRoot(i)) ans++;
        printf("Case %d: %d\n",cnt++, ans);
    }
    return 0;
}