1466:Girls and Boys

keyword

2部グラフ　最大独立点集合　C++

概要

頂点数V(<500)の2部グラフが与えられる。最大独立点集合を求める問題。
色々調べてみると、V-|最大マッチング|になるらしい。計算量O(V*E)。

int main(){
    int all;
    while(scanf("%d",&all)!=EOF){
        V = 500;
        for(int i=0; i<V; i++)
            G[i].clear();
        for(int i=0; i<all; i++){
            int v,m,u;
            scanf(" ");
            scanf("%d: (%d)",&v,&m);
            for(int j=0; j<m; j++){
                scanf("%d",&u);
                G[v].push_back(u);
            }
        }
        printf("%d\n",all-bipartite_matching());
    }
    return 0;
}