yukicoder : No.1194 Replace

こっちの方が楽じゃない？
https://yukicoder.me/problems/no/1194

問題

1～Nが1個ずつ含まれる数列Aが与えられる。
ここで、M個の操作が与えられる。
各操作では、値Bに一致する全要素をすべてCに置換することができる。

各操作を任意順任意回数行える時、数列の総和の最大値を求めよ。

解法

操作に現れない値は無視するとし、残った値について考える。
「遷移先の最大値が確定した値」が大きい順に、そこに遷移可能な値を同じ値とみなす、という処理を行おう。
強連結成分分解を行わずPriority_queueであっさり解ける。

int N,M;
map<int,vector<int>> G;
map<int,int> ma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	priority_queue<pair<int,int>> P;
	FOR(i,M) {
		cin>>x>>y;
		G[y].push_back(x);
		ma[y]=y;
		ma[x]=x;
		P.push({y,y});
	}
	while(P.size()) {
		int v=P.top().first;
		int cur=P.top().second;
		P.pop();
		if(ma[cur]!=v) continue;
		
		FORR(e,G[cur]) if(ma[e]<v) {
			ma[e]=v;
			P.push({v,e});
		}
		
	}
	
	ll ret=1LL*N*(N+1)/2;
	FORR(m,ma) ret+=m.second-m.first;
	cout<<ret<<endl;
	
}

まとめ

自分も最初「SCCか…面倒だな…」と思ったけど、これでいいじゃん、と短い解法を思いつけた。