これは連携かな。
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; } }
まとめ
問題名のセンスは結構すき。