Codeforces #192, Division 2, B : Road Construction

問題文

http://codeforces.com/contest/330/problem/B

概要

整数 N と、M 個の数のペア が与えられる。
次の条件を満たす N 頂点の無向グラフを構築せよ。

• 全ての頂点対について、二点間距離は二歩以下
• 二点 間には辺が無い

解法

基本戦略として、スター型のトポロジーをもつグラフを構築することで、一つ目の条件をクリアできます。
ただし、外縁部から中心への辺が張れない場合は、その他の外縁全てに対して辺を張る必要があります。
そのような張り方ができない場合は中心の選び方が間違いであることが言えます。
よって、中心の選び方を全探索し、上のような方法でグラフを構築します。
構築できたグラフの内、辺の数が最小のものが答えです。

……として本番では AC したのですが、M < N / 2 の制約から {tex:a_i] にも にも含まれない頂点が一つ以上存在します。
この頂点を中心にすることでスター型のグラフを構築することができます。

コード

typedef pair<int,int> PII;
typedef vector<PII> VPII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

VPII construct( const int N, const VPII &pairs, const int center )
{
	VPII res;
	REP( i, 0, N )
	{
		if ( i == center )
		{
			continue;
		}

		if ( binary_search( ALL( pairs ), MP( center, i ) ) )
		{
			REP( j, 0, N )
			{
				if ( j == i || j == center )
				{
					continue;
				}
				if ( binary_search( ALL( pairs ), MP( i, j ) ) )
				{
					return VPII( N * N );
				}
				res.PB( MP( i, j ) );
			}
		}
		else
		{
			res.PB( MP( center, i ) );
		}
	}

	sort( ALL( res ) );
	res.erase( unique( ALL( res ) ), res.end() );
	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, m;
	cin >> n >> m;

	VPII pairs;
	REP( i, 0, m )
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;

		pairs.PB( MP( a, b ) );
		pairs.PB( MP( b, a ) );
	}
	sort( ALL( pairs ) );

	VPII res( n * n );
	REP( i, 0, n )
	{
		res = min( res, construct( n, pairs, i ), []( const VPII &a, const VPII &b ){ return a.size() < b.size(); } );
	}

	cout << res.size() << endl;
	FOR( p, res )
	{
		cout << p.fst + 1 << ' ' << p.snd + 1 << endl;
	}

	return 0;
}