Educational Codeforces Round 49 D Mouse Hunt

前回のままではさすがに芸が無いからsccの応用問題を解いてみたよ
Problem - 1027D - Codeforces
強連結成分分解→強連結成分どうしの隣接リストを作ってdfsの流れで

#include<cstdio>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
static const int MAX_N = 200000;

int N;
int c[MAX_N], a[MAX_N];

vector<int> G[MAX_N];
vector<int> rG[MAX_N];
vector<int> vs;
bool used[MAX_N];
int cmp[MAX_N];

vector<int> G2[MAX_N];
int num[MAX_N];
bool visited[MAX_N];

void add_edge(int from, int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v){
	used[v] = true;
	for(int i = 0; i < G[v].size(); i++){
		if(!used[G[v][i]]) dfs(G[v][i]);
	}
	vs.push_back(v);
}

void rdfs(int v, int k){
	used[v] = true;
	cmp[v] = k;
	for(int i = 0; i < rG[v].size(); i++){
		if(!used[rG[v][i]]) rdfs(rG[v][i], k);
	}
}

int scc(){
	fill(used, used + N, false);
	vs.clear();
	for(int i = 0; i < N; i++){
		if(!used[i]) dfs(i);
	}
	fill(used, used + N, false);
	int k = 0;
	for(int i = vs.size() - 1; i >= 0; i--){
		if(!used[vs[i]]) rdfs(vs[i], k++);
	}
	return k;
}

int dfs2(int s){
	if(visited[s]) return 0;
	visited[s] = true;
	if(G2[s].size() == 0) return num[s];
	int res = 0;
	for(int i = 0; i < G2[s].size(); i++){
		if(visited[G2[s][i]]) continue;
		res += dfs2(G2[s][i]);
	}
	return res;
}

int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%d", &c[i]);
	for(int i = 0; i < N; i++){
		scanf("%d", &a[i]);
		a[i]--;
		if(i == a[i]) continue;
		add_edge(i, a[i]);
	}
	int n = scc();
	fill(num, num + n, INT_MAX);
	fill(visited, visited + n, false);
	for(int i = 0; i < N; i++){
		num[cmp[i]] = min(num[cmp[i]], c[i]);
		if(cmp[i] == cmp[a[i]]) continue;
		G2[cmp[i]].push_back(cmp[a[i]]);
	}
	int res = 0;
	for(int i = 0; i < n; i++){
		res += dfs2(i);
	}
	printf("%d\n", res);
	return 0;
}