AOJ 2291: Brilliant Stars

考察要素が大きく、実装パートも面白いので良問だと思う。

解法

完全グラフK_nのときは、自明
そうでないとき、他の全ての点と接続しているような点が存在しているから、その点を取り除く。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long ll;
typedef pair<int, int> P;
#define N 100000
#define M 200000
int a[M], b[M], d[N], e[N];
P p[N];
bool ng[N];
ll mod = 1000000009;
int main(){
	int n, m;
	scanf("%d%d",&n,&m);
	for(int i = 0; i < m; i++){
		scanf("%d%d",a+i,b+i);
		a[i]--; b[i]--;
		d[a[i]]++; d[b[i]]++;
	}
	for(int i = 0; i < n; i++) p[i] = P(-d[i], i);
	sort(p, p+n);
	for(int i = 0; i < n; i++) e[p[i].second] = i;
	vector<vector<int> > g(n);
	for(int i = 0; i < m; i++){
		int u = e[a[i]], v = e[b[i]];
		if(u>v) swap(u, v);
		g[u].push_back(v);
	}
	for(int i = 0; i < n; i++) sort(g[i].begin(), g[i].end());
	ll sum = 0, res = 1;
	for(int i = 0; i < n; i++){
		if(ng[i] || (!g[i].empty() && p[i].first!=p[g[i].back()].first)) continue;
		for(int j = 0; j < g[i].size(); j++) ng[g[i][j]] = true;
		sum++;
		res = (res*(g[i].size()+1))%mod;
	}
	printf("%ld\n%ld\n",sum,res);
	return 0;
}