TopCoder SRM 357 Div1 Medium WebsiteRank

問題

いくつかのwebサイトのリンクの関係が与えられる。
websiterankとは次のような値である。

最初、全てのサイトの値は1.
サイトAからサイトBへリンクがあるとき、サイトBの値にサイトAの値を足す。
ただし、サイトBからサイトAへ直接、または間接的にリンクがあるときは足さない。

このようにして得られる値のうち、websiteの名前のサイトの値を求めよ。

制約条件

リンクは文字列のリストの形式で与えられる。
webサイトの総数は1200くらい。

方針

ループしている部分では値を足してはいけないので、
強連結成分分解して、同じ強連結成分内のエッジは全て消すようにする。

するとDAGになるので、後は普通にDPして値を求めればいい。

入力のサイズは50だが、サイトの総数は1200くらいになりうるので注意する。

ソースコード

int n;
vector<set<int> > e, re;
bool used[2000];
int cmp[2000];
ll ans[2000];
vi vs;

void add_edge(int a, int b){
	e[a].insert(b);
	re[b].insert(a);
}
void dfs(int v){
	used[v] = 1;
	each(i, e[v]) if(!used[*i]) dfs(*i);
	vs.pb(v);
}
void rdfs(int v, int k){
	used[v] = 1;
	cmp[v] = k;
	each(i, re[v]) if(!used[*i]) rdfs(*i, k);
}
int scc(){
	memset(used, 0, sizeof(used));
	vs.clear();
	rep(v, n) if(!used[v]) dfs(v);
	memset(used, 0, sizeof(used));
	int k = 0;
	for(int i = vs.size() - 1; i >= 0; i--)
		if(!used[vs[i]]) rdfs(vs[i], k++);
	return k;
}

ll rec(int c){
	ll &res = ans[c];
	if(res >= 0) return res;
	
	res = 1;
	each(i, re[c]) res += rec(*i);
	return res;
}

class WebsiteRank {
	public:
	long long countVotes(vector <string> votes, string website) 
	{
		n = 0;
		map<string, int> id;
		
		rep(i, votes.size()){
			stringstream ss(votes[i]);
			string s;
			while(ss >> s){
				if(!id.count(s)) id[s] = n++;
			}
		}
		
		e.clear(); re.clear();
		e.resize(n); re.resize(n);
		
		rep(i, votes.size()){
			stringstream ss(votes[i]);
			string s, t;
			ss >> t;
			while(ss >> s) add_edge(id[s], id[t]);
		}
		
		int nc = scc();
		
		rep(i, nc){
			vi v;
			rep(j, n) if(cmp[j] == i) v.pb(j);
			rep(j, v.size()) rep(k, v.size())
			re[v[j]].erase(v[k]), re[v[k]].erase(v[j]),
			e[v[j]].erase(v[k]), e[v[k]].erase(v[j]);
		}
		
		rep(i, n) ans[i] = -1;
		rep(i, n) if(e[i].size() == 0) rec(i);
		
		return ans[id[website]];
	}
};