kmjp's blog

競技プログラミング参加記です

yukicoder : No.1813 Magical Stones

どっかで出てそう?
https://yukicoder.me/problems/no/1813

問題

N個の変数と、M個の条件が与えられる。
各条件では、ある変数が別の変数以上であることが示される。

全変数が同じ値であるようにするには、最低あと何個の条件を加えればよいか。

解法

U番目の変数がV番目の変数以上である、という条件を、有向グラフにおいてU→Vの辺と読み替える。
とすると、全変数が同じ値であるというのは、このグラフを強連結にすることと読み替えられる。

そこでまず元のグラフを強連結成分分解して縮約しまおう。
縮約後のグラフが2個以上の頂点からなる場合、全頂点について入次数・出次数が1以上になればよいので、入次数が0の頂点と出次数が0の頂点の間に辺を張ることにする。

int N,M;
class SCC {
public:
	static const int MV = 2025000;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0,i; SC.clear(); SC.resize(NV); NUM.clear();
		assert(NV);
		FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0;
		for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};
vector<int> E[202020];
SCC scc;
int in[202020],out[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	scc.init(N);
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		scc.add_edge(x-1,y-1);
	}
	scc.scc();
	FOR(i,N) {
		FORR(e,E[i]) if(scc.GR[i]!=scc.GR[e]) {
			in[scc.GR[e]]=1;
			out[scc.GR[i]]=1;
		}
	}
	
	if(scc.SC.size()==1) {
		cout<<0<<endl;
	}
	else {
		int nin=0,nout=0;
		FOR(i,scc.SC.size()) {
			if(in[i]==0) nin++;
			if(out[i]==0) nout++;
		}
		cout<<max(nin,nout)<<endl;
	}
	
}

まとめ

コード量はそこまでおおくないね。