사이클 검출

ㅁ 양방향 그래프

https://cses.fi/problemset/task/1669

prv배열과 사이클의 끝점, 시작점을 잘 캐치하면 된다.

 

<문제설명>

양방향 그래프가 주어질 때 사이클이 없으면 IMPOSSIBLE출력, 있으면 아무 사이클이나 사이클을 이루는 정점의 크기와 정점번호들 순서대로 출력

 

<코드>

const int MAX = 1e5 + 2;

int n, m, prv[MAX], st, en; 
vector<int> adj[MAX];
bool vst[MAX], fin[MAX];
void dfs(int curr, int pr=0) {
	vst[curr] = true;

	for (int next : adj[curr]) {
		if (!vst[next]) {
			prv[next] = curr;
			dfs(next,curr);
		}
        //다음 정점이 방문했고, dfs끝나지 않았고, 이전 정점이 아닐 경우 사이클 마지막 지점
		else if (!fin[next] && next!=pr) st=next, en=curr;
	}

	fin[curr] = true;
}

int main() {
	FAST;
	cin >> n >> m;
	int t;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		t = u;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(t); //아무정점에서나 시작해도 된다
	if (st==0) {
		cout << "IMPOSSIBLE\n";
	}
	else {
		vector<int> ans;
		while(true) {
			ans.push_back(en);
			if (en == st) break;
			en = prv[en];
		} 
		ans.push_back(ans[0]);

		cout << ans.size() << '\n';
		for (int i : ans)
			cout << i << " ";
		cout << '\n';
	}
}

 

 

---

ㅁ 방향 그래프

https://cses.fi/problemset/task/1678

위 문제와 다른 조건은 양방향인지 단방향인지 뿐

 

코드에서 다른 부분은 dfs에 이전 정점을 유지하지 않는다는 점과, ans배열의 순서를 뒤집어 출력해야 한다는 것 뿐이다.

 

<문제설명>

 방향 그래프가 주어질 때 사이클이 없으면 IMPOSSIBLE출력, 있으면 아무 사이클이나 사이클을 이루는 정점의 크기와 정점번호들 순서대로 출력

 

<코드>

const int MAX = 1e5 + 2;

int n, m, st,en, befo[MAX];
vector<int> adj[MAX];
bool vst[MAX], fin[MAX];
//단방향 그래프이므로 이전 정점을 유지할 필요 없다
void dfs(int u) {
	vst[u] = true;

	for (int v : adj[u]) {
		if (!vst[v]) {
			befo[v] = u;
			dfs(v);
		}
		else if (!fin[v]) st = v, en=u;
	}
	fin[u] = true;
}

int main() {
	FAST;
	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
	}

	for (int i = 1; i <= n; i++)
		if (!vst[i])
			dfs(i);

	if (st==0) {
		cout << "IMPOSSIBLE\n";
	}
	else {
		vector<int> ans;
		while (true) {
			ans.push_back(en);
			if (en == st) break;
			en = befo[en];
		}
		ans.push_back(ans[0]);

		//순서 생각해야 함
		reverse(ans.begin(), ans.end());

		cout << ans.size() << '\n';
		for (int i : ans)
			cout << i << " ";
		cout << '\n';
	}
}

 

---

ㅁ 음의 사이클 검출

https://cses.fi/problemset/task/1197

dfs과정에서 검출하는 사이클은 사이클의 시작점과 끝점을 알 수 있기 때문에 prv배열과 시작점, 끝점만으로 사이클을 온전히 떼어낼 수 있지만, 모든 간선에 대해 n-1번 갱신하는 밸만 포드에서는 사이클의 시작점과 끝점을 알 수 없다.

 

풀이에 쓴 아이디어를 잘 기억해두자. 이 아이디어는 위에 두 문제에도 그대로 적용할 수 있다. 좀더 범용적인 풀이라는 뜻

 

<문제설명>

단방향 음의 가중치를 허용한 그래프에서 음의 사이클이 있다면 아무 사이클이나 사이클을 이루는 정점들의 개수와 정점번호들을 순서대로 출력.

 

<풀이>

벨만 포드 과정에서 n번째 라운드에 간선이 갱신되면 음의 사이클이 있다. 이때 갱신된 간선의 양 끝점은 음의 사이클의 영향을 받는 정점이라고 할 수 있다. 따라서 이 끝점 중 아무거나 최대 n번 prv배열을 따라 가면 그 정점은 어떤 음의 사이클의 정점이다. 

 

<코드>

typedef tuple<int, int, ll> E;
const int MAX = 5e3 + 2;
const ll INF = 1e18;

int main() {
	FAST;
	int n, m; cin >> n >> m;

	E edge[MAX];
	for (ll i = 0, u, v, w; i < m; i++) {
		cin >> u >> v >> w;
		edge[i] = { u,v,w };
	}

	ll dist[MAX];
	fill(dist, dist + MAX, INF);
	dist[1] = 0;

	//밸만포드
	int befo[MAX], st=0;
	for (int k = 0; k < n; k++) {
		for (ll i = 0, u, v, w; i < m; i++) {
			tie(u, v, w) = edge[i];
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				befo[v] = u;

				//음의 사이클에 영향을 받는 점
				if(k==n-1)
					st = v;
			}
		}
	}

	if (st!=0) {
		cout << "YES\n";
		//음의 사이클에 포함된 점을 찾아간다  ***핵심***
		for (int i = 0; i < n; i++) st = befo[st];
        
		vector<int> ans;
		int t = st;
		while (true) {
			ans.push_back(t);
			t = befo[t];
			if (t == st) break;
		}
		ans.push_back(t);

		for (auto it = ans.rbegin(); it != ans.rend(); it++)
			cout << *it << " ";
		cout << '\n';
	}
	else cout << "NO\n";
}