読者です 読者をやめる 読者になる 読者になる

Code Forces 109 div2 E (div1 C)

Dの計算量見積もらなさすぎて落ちたけど、レートは上がっていた。
Div1遠いよぉw
時間中に解けなかったE問題を解きました。(非ハッシュ)

問題概要

グラフが与えられた時、他の頂点との接続関係が一致する頂点のペアの数を求めよ。
頂点数・辺数 < 10^6

僕の解法

頂点を順番に見ていき、その頂点から辺が出ているか出ていないかで各頂点をグループ分けする。
各頂点は最大で2つのグループに属しうる。
グループ分けの処理が3回も登場してたりして汚いけどソース↓

#include<cstdio>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;

const int MX = 1000005, MG = MX<<1, INF = 100000000;

int head[MX], next[MG], to[MG], g;
P gr[MX];
int st[MG], s;
int w[MG], v[MG], o[MG];
ll cnt[MG];


int main(){
	int n, m, a, b;
	scanf("%d%d",&n,&m);
	
	rrep(i,n) head[i] = -1;
	
	rep(i,m){
		scanf("%d%d",&a,&b);
		next[g] = head[a]; head[a] = g; to[g++] = b;
		next[g] = head[b]; head[b] = g; to[g++] = a;
	}
	
	m = n*2;
	rrep(i,m) st[s++] = i;
	o[0] = n*2;
	
	rrep(i,n){
		a = gr[i].se;
		w[a] = i; v[a] = st[--s];
		gr[i].se = v[a];
		o[a]--; o[v[a]]++;
		if(!o[a]) st[s++] = a;
		
		for(int j = head[i]; j != -1; j = next[j]){
			a = gr[to[j]].fi;
			if(w[a]!=i){
				w[a] = i; v[a] = st[--s];
			}
			gr[to[j]].fi = v[a];
			o[a]--; o[v[a]]++;
			if(!o[a]) st[s++] = a;
			
			a = gr[to[j]].se;
			if(w[a]!=i){
				w[a] = i; v[a] = st[--s];
			}
			gr[to[j]].se = v[a];
			o[a]--; o[v[a]]++;
			if(!o[a]) st[s++] = a;
		}
	}
	
	rrep(i,n){
		cnt[gr[i].fi]++;
		cnt[gr[i].se]++;
	}
	
	ll ans = 0;
	m++;
	rep(i,m){
		ans += cnt[i]*(cnt[i]-1)/2;
	}
	
	cout << ans;
	
	return 0;
}

ハッシュの方が楽ですね。(rngさんのソースなど参照して下さい。)
なるほどねぇ〜