CF1228D Complete Tripartite

题目链接

问题分析

要求把点分成3组，每个组内没有边，每个点和每个不属于它这组的点之间都有边。

所以嘛，每组内的点连向的边都是相同的，和$u$不相邻的点都在$u$的同一组。

考虑到只有$3$组，所以直接$O(n+m)$暴力就好。可能需要通过代码理解一下

参考程序

#include <bits/stdc++.h>
using namespace std;
 
const int Maxn = 100010;
const int Maxm = 300010;
struct edge {
	int x, y;
	edge() {}
	edge( int _x, int _y ) : x( _x ), y( _y ) {}
	inline bool operator < ( const edge Other ) const {
		return x < Other.x || x == Other.x && y < Other.y;
	}
	inline bool operator == ( const edge Other ) const {
		return x == Other.x && y == Other.y;
	}
	inline bool operator > ( const edge Other ) const {
		return x > Other.x || x == Other.x && y > Other.y;
	}
};
int n, m;
edge Edge[ Maxm << 1 ];
int Color[ Maxn ], App[ Maxn ], Cnt;
 
int main() {
	scanf( "%d%d", &n, &m );
	for( int i = 1; i <= m; ++i ) scanf( "%d%d", &Edge[ i ].x, &Edge[ i ].y );
	for( int i = 1; i <= m; ++i ) Edge[ i + m ] = edge( Edge[ i ].y, Edge[ i ].x );
	m <<= 1;
	sort( Edge + 1, Edge + m + 1 );
	for( int i = 1; i <= n; ++i ) {
		if( Color[ i ] ) continue;
		++Cnt;
		if( Cnt > 3 ) {
			printf( "-1
" );
			return 0;
		}
 
		memset( App, 0, sizeof( App ) );
		int l = upper_bound( Edge + 1, Edge + m + 1, edge( i, 0 ) ) - Edge;
		int r = l - 1;
		while( Edge[ r + 1 ].x == i ) {
			++r;
			App[ Edge[ r ].y ] = 1;
		}
//		printf( "l = %d, r = %d
", l, r );
//		printf( "A %d
", i );
//		printf( "App : " ); for( int j = 1; j <= n; ++j ) printf( "%d ", App[ j ] ); printf( "
" );
//		for( int j = l; j <= r; ++j ) printf( "%d %d
", Edge[ j ].x, Edge[ j ].y );
 
		for( int j = 1; j <= n; ++j ) {
			if( App[ j ] == 0 && Color[ j ] != 0 ) {
				printf( "-1
" );
				return 0;
			}
			if( App[ j ] ) continue;
			Color[ j ] = Cnt;
			int L = upper_bound( Edge + 1, Edge + m + 1, edge( j, 0 ) ) - Edge;
			for( int k = l; k <= r; ++k ) {
				int R = L + ( k - l );
//				printf( "k = %d, R = %d, r = %d
", k, R, l + ( k - l ) );
				if( Edge[ R ].x != j || Edge[ R ].y != Edge[ l + ( k - l ) ].y ) {
					printf( "-1
" );
					return 0;
				}
			}
		}
//		printf( "A %d
", i );
//		for( int j = 1; j <= n; ++j ) printf( "%d ", Color[ j ] ); printf( "
" );
	}
	if( Cnt != 3 ) {
		printf( "-1
" );
		return 0;
	}
	for( int i = 1; i <= n; ++i ) printf( "%d ", Color[ i ] ); printf( "
" );
	return 0;
}