TOJ 275 同學會 ( Adhoc )

http://sprout.tw/oj/pro/275/
這題雖然看起來很簡單，卻要想清楚很多細節才能寫好。最重要的關鍵是要發現如何做才能快速地發現那個團體中最後一個人。如果我們對每個團體紀錄 id的總和，剩下的人數，每次減少一個人就從 id總和減去它的 id，就能夠在刪除某個人後快速發現哪些人符合條件。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000 + 3;
const int MAXM = 3000 + 3;

int n, m;
vector<int> belong_party[ MAXN ];
vector<int> party[ MAXM ];
int party_sum_id[ MAXM ], party_sure_cnt[ MAXM ];
int k;
int sure[ MAXN ];

void recursiveRemove(int x){
    if( sure[ x ] ) return;
    sure[ x ] = 1;
    for(int p: belong_party[ x ]){
        party_sum_id[ p ] -= x;
        if( --party_sure_cnt[ p ] == 1 )
            recursiveRemove( party_sum_id[ p ] );
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i){
        int s; scanf("%d", &s);
        for(int j = 0; j < s; ++j){
            int x; scanf("%d", &x);
            party[ i ].push_back( x );
            belong_party[ x ].push_back( i );
            party_sum_id[ i ] += x;
        }
        party_sure_cnt[ i ] = s;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; ++i){
        int x; scanf("%d", &x);
        if( sure[ x ] ) continue;
        sure[ x ] = 1;
        for(int p: belong_party[ x ]){
            party_sum_id[ p ] -= x;
            if( --party_sure_cnt[ p ] == 1 )
                recursiveRemove( party_sum_id[ p ] );
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i)
        ans += sure[ i ];
    printf("%d\n", ans);
    return 0;
}