IOPC12-IOPC1213 : Colouring graphs

codechef

問題概要

ノード数N(<100)のグラフがある。Q(<1000)個のクエリがあって、

  1. 辺を追加する
  2. 辺を削除する
  3. K(>1)彩色の仕方が何通りあるか出力する

を処理する。ただしグラフは常に森である。

解法

答えは、各連結成分に対してK*(K-1)^(size-1)をかけ合わせる。
連結成分の個数とサイズを求めるのは、制約が緩いので愚直に処理して間に合う。
実はサイズを求める必要はない(K^C * (K-1)^(N-C) が答。Cは連結成分の個数)。

acceptされたコード

計算量O(N+Q^2)。

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

typedef long long int64;

const int MAX_N = 100;
const int64 MOD = 100000007;

int N, M, Q;
vector<int> graph[MAX_N];
bool visited[MAX_N];

int64 pow_binary(int64 x, int n){
	int64 ret = 1;
	for(;n;n>>=1){
		if( n&1 ){
			ret = ret * x % MOD;
		}
		x = x * x % MOD;
	}

	return ret;
}

void init(){
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=0; i<N; i++){
		graph[i].clear();
	}

	for(int i=0; i<M; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
}

void add(){
	int x, y;
	scanf("%d%d", &x, &y);
	graph[x].push_back(y);
	graph[y].push_back(x);
}

void del(){
	int x, y;
	scanf("%d%d", &x, &y);

	for(int k=0; k<2; k++){
		vector<int> tmp;
		for(int i=0; i<(int)graph[x].size(); i++){
			if(graph[x][i] != y){
				tmp.push_back(graph[x][i]);
			}
		}
		graph[x] = tmp;
		swap(x, y);
	}
}

int dfs(int v){
	visited[v] = true;
	int ret = 1;
	for(int i=0; i<(int)graph[v].size(); i++){
		const int u = graph[v][i];
		if(!visited[u]){
			ret += dfs(u);
		}
	}
	return ret;
}

int count(int k){
	memset(visited, false, sizeof(visited));
	int64 ans = 1;
	for(int i=0; i<N; i++)if(!visited[i]){
		int sz = dfs(i);
		ans = ans * k % MOD;
		ans = ans * pow_binary(k-1, sz-1) % MOD;
	}
	return (int)ans;
}

void query(){
	int k;
	scanf("%d", &k);
	if(k==0){
		add();
	}
	else if(k==1){
		del();
	}
	else{
		printf("%d\n", count(k));
	}
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		for(int i=0; i<Q; i++){
			query();
		}
	}

	return 0;
}