問題概要
有向グラフ G が family graph であるとは、次の条件を充足することであるとする。
- 各頂点は男性か女性である
- 頂点 v から頂点 u に有向辺があるとき、v は u の親である
- ある頂点が親をもつとき、親の数は丁度二つである
- ある頂点が親をもつとき、二つの親の性別は異なる
与えられる有向グラフを family graph にするような性別の割り当てが存在するかどうか、求めよ。
解法
与えられたグラフについて、次のように辺を張り替えたグラフを考えます。
- 二頂点の性別が異ならなければならないとき、その二頂点間に辺を張る
このとき、元のグラフを family graph にできることと、新しいグラフが二部グラフであることは同値です。従って、このグラフ上で DFS などをして二部グラフか否かを判定することで問題を解くことができます。
コード
using VI = vector<int>; using VVI = vector<VI>; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( e, c ) for ( auto &e : c ) #define PB( n ) push_back( n ) class Family { public: string isFamily( vector <int> parent1, vector <int> parent2 ) { const int N = parent1.size(); VVI G( N ); VI colors( N, -1 ); REP( i, 0, N ) { if ( parent1[i] != -1 && parent2[i] != -1 ) { G[ parent1[i] ].PB( parent2[i] ); G[ parent2[i] ].PB( parent1[i] ); } } REP( i, 0, N ) { if ( colors[i] == -1 && !paint( G, colors, i, 0 ) ) { return "Impossible"; } } return "Possible"; } bool paint( const VVI &G, VI &colors, const int v, const int c ) { if ( colors[v] != -1 ) { return colors[v] == c; } colors[v] = c; FOR( u, G[v] ) { if ( !paint( G, colors, u, 1 - c ) ) { return false; } } return true; } };