概要
N 個の瓶があり、それぞれの瓶のメーカーは であり、それを用いて他の 製の瓶を開けることができる。
(開けるのに使う瓶は必ずしも開いていなくてもよい)
開けられない瓶の数を求めよ。
解法
(ただし ) となる i, j の組が一つでもあれば、i 番目の瓶を開けることができると分かります。
i, j についての二重ループで全通り試せば解けます。
コード
typedef vector<int> VI; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int n; cin >> n; VI as( n ), bs( n ); REP( i, 0, n ) { cin >> as[i] >> bs[i]; } vector<bool> openalbe( n, false ); REP( i, 0, n ) { REP( j, 0, n ) { if ( i == j ) { continue; } openalbe[j] = openalbe[j] | bs[i] == as[j]; } } cout << count( ALL( openalbe ), false ) << endl; return 0; }