Codeforces #286 Div1 B. Mr. Kitayuta's Technology

これは自分で解法を思いついたとき、おおって思った。
http://codeforces.com/contest/506/problem/B

問題

N頂点からなる有向グラフを構築したい。

ここでM個の条件(A[i],B[i])が与えられる。
各条件は、構築した有効グラフにおいてA[i]からB[i]に至るパスがある必要があることを示す。

全ての条件を満たす最小の有向辺数を答えよ。

解法

まず条件を有向辺でなく無向辺と見なしUnion-Findで連結成分を求める。

各連結成分に置いて必要な有向辺数を求める。

基本的には(無向辺の)連結成分がP点あるなら、それらをトポロジカルソートして(P-1)本の辺で結べば良い。
ただし、P点中に１か所でも閉路が必要になるなら、P本の辺でP点全体を閉路にすればよい。

実際はトポロジカルソートそのものは不要で、強連結成分分解で閉路の存在を検索すればよい。

class SCC {
public:
	static const int MV = 101000;
	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<MV;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; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); 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);
	}
};

class UF {
	public:
	static const int ufmax=100052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));}
	int count(int x) { return ufcnt[operator[](x)];}
	void unite(int x,int y) {
		x = operator[](x); y = operator[](y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N,M;
int A[101000],B[101000],C[101000];
vector<int> E[101000];
SCC sc;
int ret;
UF uf;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	sc.init(N);
	FOR(i,M) {
		cin>>A[i]>>B[i];
		sc.add_edge(A[i]-1,B[i]-1);
		uf.unite(A[i]-1,B[i]-1);
	}
	
	FOR(i,N) if(uf[i]!=i) ret++;
	
	sc.scc();
	FOR(i,sc.SC.size()) {
		if(sc.SC[i].size()>1 && C[uf[sc.SC[i][0]]]==0) {
			ret++;
			C[uf[sc.SC[i][0]]]=1;
		}
	}
	cout<<ret<<endl;
}

まとめ

１か所でも閉路がありそうなら、全体を閉路にすればいいっていうの、面白い特性だな。