2419:Forests

keyword

集合　C++

概要

要素が[1..T](T<100)である集合がP(<100)個与えられる。このとき、この集合族の濃度を求める問題。
要素が小さいのでどうとでもなる。多分setに突っ込んでset< set >に突っ込むのでも余裕で間に合う(これだと計算量O(T^2*log T * P * log(P))。setは定数が重いのでvectorでuniqueとか使って定数分早くした。多分union-findとか使えば(使わなくても)O(T^2*P)までは落ちると思う。

int main(){
    int T, P, i, j;
    scanf("%d%d",&P,&T);
    vector< vector<int> > vs(P);
    while(scanf("%d%d",&i,&j)!=EOF){
        vs[i-1].push_back(j);
    }
    for(i=0; i<P; i++){
        sort(vs[i].begin(), vs[i].end());
        vs[i].erase(unique(vs[i].begin(), vs[i].end()), vs[i].end());
    }
    sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    printf("%d\n",(int)vs.size());
}