yukicoder : No.2464 To DAG

これはすんなり。
https://yukicoder.me/problems/no/2464

問題

無向グラフが与えられる。
いくつか辺を取り除き、以下のようにしたい。

• 閉路を含まない
• 元のグラフと、各点で入次数・出次数の差は変化しない

可能なら一例を示せ。

解法

閉路を検出次第、その閉路を取り除けばよい。
DFSしながら閉路を見つけたらその閉路を取り除こう。
また、DFSの過程で葉に行きついてしまったら1つ戻る。その際戻った辺は、最終的な辺に組み込む、とすればよい。

int N,M;
vector<int> E[303030];
vector<pair<int,int>> R;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
	}
	
	
	FOR(i,N) {
		vector<int> V;
		set<int> S;
		V.push_back(i);
		S.insert(i);
		while(V.size()) {
			while(E[V.back()].size()) {
				x=E[V.back()].back();
				E[V.back()].pop_back();
				if(S.count(x)) {
					while(V.back()!=x) {
						S.erase(V.back());
						V.pop_back();
					}
					continue;
				}
				S.insert(x);
				V.push_back(x);
			}
			if(V.size()>=2) {
				S.erase(V.back());
				R.push_back({V[V.size()-2]+1,V[V.size()-1]+1});
			}
			V.pop_back();
		}
	}
	cout<<N<<" "<<R.size()<<endl;
	FORR2(a,b,R) cout<<a<<" "<<b<<endl;
	
}

まとめ

割とシンプルな問題設定だけど、過去にはなかったのかな。