kmjp's blog

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

yukicoder : No.2301 Namorientation

これは連携かな。
https://yukicoder.me/problems/no/2301

問題

N点N辺の連結無向グラフが与えられる。
各辺に向きをつけ、function graphとなるようにせよ。

解法

次数1の点があれば、その点につながる辺を、その点を始点とするように向きを付けたうえで取り除く、という作業を繰り返す。
最後には閉路が1つ残るので、どちらかの回り方に沿って向きをつければよい。

int N;
int A[202020],B[202020];
set<int> S[202020];
int E[202020];

void dfs(int cur) {
	while(S[cur].size()) {
		int e=*S[cur].begin();
		E[cur]=e;
		S[cur].erase(e);
		S[e].erase(cur);
		dfs(e);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		A[i]--,B[i]--;
		S[A[i]].insert(B[i]);
		S[B[i]].insert(A[i]);
	}
	queue<int> Q;
	FOR(i,N) if(S[i].size()==1) Q.push(i);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		y=*S[x].begin();
		E[x]=y;
		S[x].erase(y);
		S[y].erase(x);
		if(S[y].size()==1) Q.push(y);
	}
	
	FOR(i,N) if(S[i].size()) dfs(i);
	
	FOR(i,N) {
		if(E[A[i]]==B[i]) cout<<"->"<<endl;
		else cout<<"<-"<<endl;
	}
}

まとめ

問題名のセンスは結構すき。