CodeChef-BEARS : Bears and Bees

問題概要

G=(V,E)からG'を以下のように得る。G'=(V',E')とすると、V'=Eで、辺aと辺bがGで同じ頂点に接続していたら(a,b) in E'となる。今、グラフG[0]=(V,E)(|V|, |E|<1000)がある。G[0]を変換してG[1]を得る。G[1]を変換してG[2]を得る。G[2]を変換してG[3]を得る。G[3]の頂点数と辺数を求める問題。

解法

まず、|E|<1000なのでG[1]は陽に持てる(らしいけど実際は定数倍でTLEした)。次に、G[2]の次数列を計算する。G[2]の次数列が計算できたらG[3]の頂点数が分かる(次数列の和の半分)。また、G[3]の次数列そのものは分からなくてもG[3]の次数列の和はsum d[i]*(d[i]-1)で求めることができるので、G[3]の頂点数はG[3]の次数列の和の半分となる。

acceptされたコード

計算量O(M^2)。

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

const int MAX_N = 1000;
const int MAX_M = 1000;
const int MAX_L = 500000;

int N0, M0;
vector<int> g0[MAX_N];
pair<int,int> p0[MAX_M];
vector<int> g1[MAX_M];
int gg1[MAX_M];
pair<int,int> p1[MAX_L];

int to_idx[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

int deg2[MAX_L];

void init(){
	scanf("%d%d",&N0, &M0);
	memset(to_idx, 0, sizeof(to_idx));
	memset(deg2, 0, sizeof(deg2));
	memset(gg1, 0, sizeof(gg1));
	memset(visited, false, sizeof(visited));

	for(int i=0; i<N0; i++){
		g0[i].clear();
	}

	for(int i=0; i<M0; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		x--; y--;
		g0[x].push_back(y);
		g0[y].push_back(x);
		p0[i] = make_pair(x, y);
		to_idx[x][y] = to_idx[y][x] = i;
	}
}

void solve(){

	int N1 = M0, M1 = 0, pp = 0;
	for(int i=0; i<N1; i++){
		int x = p0[i].first, y = p0[i].second;
		for(int j=0; j<(int)g0[x].size(); j++){
			if(g0[x][j]!=y){
				gg1[i]++;
				M1++;
				if(to_idx[x][g0[x][j]] > i && !visited[i][to_idx[x][g0[x][j]]]){
					visited[i][to_idx[x][g0[x][j]]] = true;
					p1[pp++] = make_pair(i, to_idx[x][g0[x][j]]);
				}
			}
		}
		for(int j=0; j<(int)g0[y].size(); j++){
			if(g0[y][j]!=x){
				gg1[i]++;
				M1++;
				if(to_idx[y][g0[y][j]] > i && !visited[i][to_idx[y][g0[y][j]]]){
					visited[i][to_idx[y][g0[y][j]]] = true;
					p1[pp++] = make_pair(i, to_idx[y][g0[y][j]]);
				}
			}
		}
	}

	M1 /= 2;

	int N2 = M1, M2 = 0;

	for(int i=0; i<N2; i++){
		int x = p1[i].first, y = p1[i].second;
		deg2[i] += gg1[x]+gg1[y]-2;
		M2 += deg2[i];
	}
	M2 /= 2;

	long long ans = 0;
	for(int i=0; i<N2; i++){
		ans += (long long)deg2[i]*(deg2[i]-1);
	}

	printf("%d %lld\n", M2, ans/2);
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		solve();
	}

	return 0;
}