cf #656 div3 E - Directing Edges(위상정렬, 사이클 유무)

https://codeforces.com/contest/1385/problem/E

 

방향그래프와 무향그래프가 섞인 그래프에서 위상정렬을 구해야 해서 헷갈렸다.

 

위상정렬 결과로 사이클 판단하는 방법도 숙지해 뒀어야 하는 문제

 

 

 

<문제설명>

정점u,v사이엔 최대 하나의 무향또는 유향간선만 존재하는 그래프가 주어진다.

 

유향간선을 적절히 조정해서 accyclic그래프를 만들 수 있다면 그 간선들을 출력하라

 

 

<풀이>

손으로 좀 그리다보면 유향간선만 가지고 사이클이 존재하지 않는다면 항상 정답이 존재함을 알 수 있다.

 

유향간선 기준 ind로 topological sort를 한 순서벡터로 각 정점마다 순서를 매긴다.

 

유향간선 u->v 중 rank[u]>rank[v]인 경우가 존재하면 사이클이 있다는 것 의미함.

 

사이클이 없다면 ,모든 간선을 보며 {u,v}또는 {v,u}를 rank[u]>rank[v]결과에 따라 출력하면 된다.

 

 

위상정렬 시 들어오는 간선이 없지만 무향그래프가 연결된 정점은 언제 처리되든 상관이 없다.

 

 

<dfs로 순서만든 코드> -dfs탐색이 끝난 순서대로 위상정렬가능

int n, m, vst[MAX], pos[MAX];
vector<P> edge;
vector<int> g[MAX], ord;

void init() {
	edge.clear();
	ord.clear();
	for (int i = 1; i <= n; i++) g[i].clear();
}

void dfs(int u) {
	vst[u] = 1;
	for (int v : g[u]) if (!vst[v]) dfs(v);
	ord.push_back(u);
}

void solve() {
	cin >> n >> m;
	init();
	for (int i = 0, t, u, v; i < m; i++) {
		cin >> t >> u >> v;
		if (t == 1) g[u].push_back(v);
		edge.push_back({ u,v });
	}

	fill(vst, vst + n + 1, 0);
	for (int i = 1; i <= n; i++) if (!vst[i]) dfs(i);
	reverse(ord.begin(), ord.end());

	fill(pos, pos + n + 1, 0);
	for (int i = 0; i < n; i++) pos[ord[i]] = i;

	bool cycle = 0;
	for (int i = 1; i <= n; i++) {
		for (int v : g[i]) if (pos[i] > pos[v]) cycle = 1;
	}

	if (cycle) {
		cout << "NO\n";
	}
	else {
		cout << "YES\n";
		for (P p : edge) {
			int x = p.first, y = p.second;
			if (pos[x] < pos[y])
				cout << x << " " << y << '\n';
			else
				cout << y << " " << x << '\n';
		}
	}
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) solve();
}

 

 

<큐로 순서만든 코드>

int n, m, vst[MAX], pos[MAX];
vector<P> edge;
vector<int> g[MAX], ord, ind;

void init() {
	edge.clear();
	ind.clear();
	ind.resize(n + 1);
	for (int i = 1; i <= n; i++) g[i].clear();
}

void solve() {
	cin >> n >> m;
	init();
	for (int i = 0, t, u, v; i < m; i++) {
		cin >> t >> u >> v;
		if (t == 1) {
			g[u].push_back(v);
			ind[v]++;
		}
		edge.push_back({ u,v });
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) if (ind[i] == 0) q.push(i);

	ord.clear();
	while (!q.empty()) {
		int u = q.front(); q.pop();
		ord.push_back(u);
		for (int v : g[u]) {
			if (--ind[v] == 0) q.push(v);
		}
	}
	
	if (ord.size() == n) {
		fill(pos, pos + n + 1, 0);
		for (int i = 0; i < n; i++) pos[ord[i]] = i;
	}

	bool cycle = ord.size()!=n;
	for (int i = 1; i <= n; i++) {
		for (int v : g[i]) if (pos[i] > pos[v]) cycle = 1;
	}

	if (cycle) {
		cout << "NO\n";
	}
	else {
		cout << "YES\n";
		for (P p : edge) {
			int x = p.first, y = p.second;
			if (pos[x] < pos[y])
				cout << x << " " << y << '\n';
			else
				cout << y << " " << x << '\n';
		}
	}
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) solve();
}