강한 연결 요소(SCC, Strongly connected components) 문제들

* 강한 연결 요소(SCC, Strongly connected components) 문제들

  Topological sort, dynamic programming, DSU 등 다양한 알고리즘과 연결하여 풀 수 있는 문제들을 Random하게 소개해 보겠당.

1. 백준 온라인 저지

  1-1. Strongly connected component(https://www.acmicpc.net/problem/2150)

  기본적인 SCC 문제다. 모든 SCC를 저장하고 이를 정렬하여 출력하면 된다.

- 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int min_v(int a, int b) { return a < b ? a : b; }
vector<vector<int>> adj;
int *vnum, vcnt=1;
bool *finished;
stack<int> stk;
vector<vector<int>> ans;
int scc(int n) {
	int ret = vnum[n] = vcnt++;
	stk.push(n);
	for (int v : adj[n]) {
		if (vnum[v] == 0) ret = min_v(ret, scc(v));
		else if (!finished[v]) ret = min_v(ret, vnum[v]);
	}

	if (ret == vnum[n]) {
		vector<int> res;
		while (1) {
			int t = stk.top();
			stk.pop();
			res.push_back(t);
            finished[t] = 1;
			if (t == n) break;
		}
		sort(res.begin(), res.end());
		ans.push_back(res);
	}
	return ret;
}
int main() {
	int V, E, u, v, i;
	scanf("%d%d", &V, &E);
	vnum = new int[V] {};
	finished = new bool[V] {};
	adj.resize(V);
	while (E--) {
		scanf("%d%d", &u, &v);
		u--, v--;
		adj[u].push_back(v);
	}
	for (i = 0; i < V; i++)
		if(vnum[i] == 0) scc(i);
	sort(ans.begin(), ans.end());
	printf("%d\n", ans.size());
	for (vector<int>& r : ans) {
		for (int rr : r) printf("%d ", rr+1);
		printf("-1\n");
	}
	return 0;
}

  1-2. 도미노 (https://www.acmicpc.net/problem/4196)

  도미노 특성을 생각해보자. A를 넘어뜨리면 B를 넘어뜨린다고 가정한다면, 과연 B를 넘어뜨린다고해서 A가 넘어질까? 그럴 수 있을 수도 있고, 없을 수도 있다. B의 길이에 따라 결과가 달라지기 때문이다. 따라서 주어지는 입력은 방향 그래프로 구성할 수 있음을 알 수 있다.

  상황을 정리해보자. 

  1. 사이클을 이루는 경우를 생각해보면 사이클 중 하나만 쓰려뜨려도 모두가 쓰러짐을 알 수 있다.

  2. 사이클끼리 집합으로 묶고, 그 집합에 대해서 DAG를 구성하면 집합과 집합 간의 관계가 존재함을 알 수 있다. 이 성질을 이용하여 어떤 도미노 집합이 쓰러지면 다른 도미노 집합도 쓰러지는지 판단한다.

  

  따라서 SCC로 집합을 생성하여, 이 집합 간의 진입 차수를 계산하여 진입 차수가 없는 집합의 개수가 답이 됨을 알 수 있다.

- 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#include <cstring>
using namespace std;
const int MAX_V = 100001;
int min_v(int a, int b) { return a < b ? a : b; }
int sccId[MAX_V], discovered[MAX_V], sccCnt, disCnt;
vector<vector<int>> adj;
stack<int> stk;
int dfs(int u) {
	int ret = discovered[u] = disCnt;
	disCnt++;
	stk.push(u);
	for (int& v : adj[u]) {
		if (!discovered[v])
			ret = min_v(ret, dfs(v));
		else if(!sccId[v])
			ret = min_v(ret, discovered[v]);
	}

	if (ret == discovered[u]) {
		while (1) {
			int t = stk.top(); stk.pop();
			sccId[t] = sccCnt;
			if (t == u) break;
		}
		sccCnt++;
	}
	return ret;
}
int main() {
	int T,N, M, x, y, i, ans, ind[MAX_V];
	scanf("%d", &T);
	while (T--) {
		
		scanf("%d%d", &N, &M);
		adj.clear();
		adj.resize(N);
		while (M--) {
			scanf("%d%d", &x, &y);
			x--, y--;
			adj[x].push_back(y);
		}
		memset(discovered, 0, sizeof discovered);
		memset(sccId, 0, sizeof sccId);
		memset(ind, 0, sizeof ind);
		sccCnt = disCnt = 1;
		for (i = 0; i < N; i++)
			if (!discovered[i]) dfs(i);
		for (i = 0; i<N; i++)
			for (int& v : adj[i]) {
				if (sccId[i] != sccId[v])
					ind[sccId[v]]++;
			}
		ans = 0;
		for (i = 1; i < sccCnt; i++)
			if (!ind[i]) ans++;
		printf("%d\n", ans);
	}
	
	return 0;
}

  1-3. ATM (https://www.acmicpc.net/problem/4013)

    [분류 - SCC/ Topological sort/ Dynamic programming/BFS ]  

  먼저 일방통행 도로이기 때문에 방향 그래프임을 알 수 있다.

  같은 도로를 여러번 방문할 수 있기 때문에 도시들이 사이클을 이루는지 판단하여 그 안에 있는 도시를 모두 방문할 수 있음을 알 수 있다.

  하나의 도시 사이클에 대해 다른 도시 사이클에서 올 수 있는 방법이 여러 방법이 있을 수 있기 때문에 dynamic을 사용해야 한다.

- 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX_V = 500001;
int max_v(int a, int b) { return a > b ? a : b; }
int min_v(int a, int b) { return a < b ? a : b; }
int sccId[MAX_V], discovered[MAX_V], sccCnt = 1, disCnt = 1;
int money[MAX_V], dp[MAX_V], sccM[MAX_V];
vector<int> topological_sort;
vector<vector<int>> adj;
vector<set<int>> adjscc;
stack<int> stk;
int dfs(int u) {
	int ret = discovered[u] = disCnt;
	disCnt++;
	stk.push(u);
	for (int& v : adj[u]) {
		if (!discovered[v])
			ret = min_v(ret, dfs(v));
		else if (!sccId[v])
			ret = min_v(ret, discovered[v]);
	}

	if (ret == discovered[u]) {
		while (1) {
			int t = stk.top(); stk.pop();
			sccId[t] = sccCnt;
			sccM[sccCnt] += money[t];
			if (t == u) break;
		}
		sccCnt++;
	}
	return ret;
}
int main() {
	int i, N, M, u, v, S, P;
	scanf("%d%d", &N, &M);
	adj.resize(N);
	while (M--) {
		scanf("%d%d", &u, &v);
		u--, v--;
		adj[u].push_back(v);
	}
	for (i = 0; i < N; i++) scanf("%d", &money[i]);
	scanf("%d%d", &S, &P);
	S--;

	dfs(S);
	adjscc.resize(sccCnt+1);
	for (i = 0; i < N; i++)
		for (int& v : adj[i]) {
			if (sccId[i] && sccId[v] && sccId[i] != sccId[v])
				adjscc[sccId[i]].insert(sccId[v]);
		}
	queue<int> q;
	q.push(sccId[S]);
	dp[sccId[S]] = sccM[sccId[S]];
	while (!q.empty()) {
		u = q.front(), q.pop();
		for(auto it = adjscc[u].begin(); it!= adjscc[u].end();it++)
			if (dp[*it] < dp[u] + sccM[*it]) {
				dp[*it] = dp[u] + sccM[*it];
				q.push(*it);
			}
	}
	int ans = 0;
	while (P--) {
		scanf("%d", &u);
		u--;
		ans = max_v(ans, dp[sccId[u]]);
	}
	printf("%d", ans);
	return 0;
}

1-4. 동치 증명 (https://www.acmicpc.net/problem/3682)

    [분류 - SCC/ Greedy algorithm ]

  상당히 재밌는 문제. 

  1. 먼저 주어진 명제 중에서 일부분이 사이클을 이룬다면 그 사이클 내에서 다시금 증명할 필요는 없다.

즉 A->B, B->C, C->D, D->A라면 D->B 를 증명할 필요는 없다.

  2. 모든 명제가 동치를 이루기 위해서는 임의의 한 명제 A에서 다른 명제 B로 갈 수 있는 증명 경로가 있어야 한다. 이는 곧 SCC의 특성이 되며, 곧 사이클을 이뤄야 함을 알 수 있다. 따라서 모든 명제는 하나의 사이클을 이뤄야 가능하다.

  위 사실을 통해 최소한의 증명을 사용하기 위해 먼저 주어진 명제들이 사이클을 이루는지 확인해야 한다. 이는 SCC를 통해 집합 단위로 묶을 수 있다.

  집합 단위로 묶고나면 이 사이클 집합이 전체적으로 사이클을 이룬다면 모든 명제가 사이클을 이루는 것을 알 수 있다.

  그렇다면 이 집합들이 사이클을 이루기 위해서는 모든 집합에 대해 진입 차수와 진출 차수가 0이 아니어야 하고, 추가되는 증명(간선)들이 짜임새 있게 구성이 되어야 한다. 우선 사이클 집합에 대해 진입 차수가 0인 것과 진출 차수가 0인 것은 쉽게 파악할 수 있다.

  문제가 요구하는 것은 "어떻게 증명할 것인가"가 아니라 "얼마나 적게 증명할 수 있냐"이기 때문에, 아래와 같은 상황에서 진입 차수가 0인 집합과 진출 차수가 0인 집합을 Greedy하게 연결시킬 수 있다.

  이렇게 하면 연결된 집합에 대해서 모두 사이클을 이룸을 알 수 있다. (C와 A를 이어줄 수는 없다. 하지만 이를 고려하지 않아도 된다. 우리는 그저 필요한 증명의 수 자체가 궁금하기 때문에)

  나머지 할 일은 진입 또는 진출 차수가 남을 수도 있는데(그림에서 E 정점) 이를 임의의 사이클을 이루고 있는 집합에 연결시켜주면 된다. 따라서 전체 집합에 대해 진입 또는 진출 차수가 0인 것 중 큰 값이 증명(간선)을 해야하는 수가 된다.

- 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#include <cstring>
using namespace std;
int min_v(int a, int b) { return a < b ? a : b; }
int max_v(int a, int b) { return a > b ? a : b; }
const int MAX_V = 20001;
vector<vector<int>> adj;
stack<int> stk;
int sccId[MAX_V], discovered[MAX_V], sccCount, discCount;
int scc(int u) {
	stk.push(u);
	int ret = discovered[u] = discCount;
	discCount++;
	for (int& v : adj[u]) {
		if (discovered[v] == -1)
			ret = min_v(ret, scc(v));
		else if (sccId[v] == -1)
			ret = min_v(ret, discovered[v]);
	}

	if (ret == discovered[u]) {
		while (1) {
			int t = stk.top();
			stk.pop();
			sccId[t] = sccCount;
			if (t == u) break;
		}
		sccCount++;
	}
	return ret;
}

int main() {
	int N, M, T, s1, s2, i, ans, ind[MAX_V], outd[MAX_V], inc,outc;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &N, &M);
		while (!stk.empty()) stk.pop();
		adj.clear(); adj.resize(N);
		ans = sccCount = discCount = 0;
		memset(sccId, -1, sizeof sccId);
		memset(discovered, -1, sizeof discovered);
		while (M--) {
			scanf("%d%d", &s1, &s2);
			s1--, s2--;
			adj[s1].push_back(s2);
		}
		
		for (i = 0; i < N; i++)
			if (discovered[i] == -1) scc(i);
		
		memset(ind, 0, sizeof ind);
		memset(outd, 0, sizeof outd);
		for (i = 0; i < N; i++) {
			for (int& v : adj[i])
				if (sccId[i] != sccId[v]) {
					outd[sccId[i]]++;
					ind[sccId[v]]++;
				}
		}
		inc = outc = 0;
		for (i = 0; i < sccCount; i++) {
			if (!ind[i]) inc++;
			if (!outd[i]) outc++;
		}
		printf("%d\n", sccCount == 1 ? 0 : max_v(inc, outc));
	}
	
	return 0;
}

  1-5. MT (https://www.acmicpc.net/problem/10265)

      [ 분류 - SCC/ Dynamic programming(Knapsack)/ DSU/ BFS,DFS ]

  Description만 빼면 괜찮은 문제..? 라고 생각한다. 설명이 너무 좀 생략된 것이 많은 것 같다.

  요약하자면 "A가 안가면 나도 안가"라는 문구는 "A가 가면 갈 수도 있고, 안 갈 수도 있다."를 말한다고 한다. 즉 가든 안가든 상관은 없지만 어찌됐든 A가 안간다면 가지 않겠다는 소리다.

  그래프 구조는 매우 심플하다. 여기에 대해 증명할 것이 하나 있다.

* 각 Component의 종단 지점은 반드시 사이클을 이루는 곳이다.

  

  만약 종단 지점이 사이클이 아니라면, 해당 지점은 다른 곳을 가리키기 때문에 종단 지점이 될 수 없는 모순이 발생한다.

  따라서 이 그래프 구조에서는 종단 지점은 반드시 사이클을 이룬다.

  전제 조건이 또 있다.

     * 각 Component 안에는 반드시 하나의 사이클만을 갖는다.

  서로 다른 사이클에 대해 연결되어 있다면, 하나의 정점이 두 개 이상의 간선을 가지고 있다는 소리인데, 이는 문제 주어진 형식이 아니므로 존재할 수 없는 구조다.

  이제 하나의 Component를 생각해보자. 종단 지점에 있는 사이클 집합을 A라고 가정하면, A 중 하나라도 안간다면, Component에 속한 모든 구성원은 소풍을 가지 않는다. 반대로 A 중 하나라도 간다면 "적어도" 이 사이클 집합 안에 있는 구성원은 간다고 할 것이다. 따라서 해당 Component의 가는 경우에 최소값은 사이클 집합의 크기가 된다.

  최소 인원을 구했으니, 최대 인원은 몇일까? 최대 인원은 그대로 Component의 크기가 된다. 이유는 그래프 구조상 인원 하나를 추가하는 것은 연결된 정점을 하나 셈(Count)하는 것이므로 최소 인원부터 Component 크기까지 선택할 수 있기 때문이다.

  Component의 최대 크기는 DFS를 이용해도 되고, BFS를 이용해도 된다. 나는 종단 지점의 특성을 이용하여 DSU를 이용하여 크기를 구했다.

  이후 모든 Component에 대해 순회하며 최소와 최대값을 활용하여 최대 k 명까지 태울 수 있으므로, knapsack 알고리즘을 사용하면 된다.

- 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#include <cstring>
using namespace std;
int min_v(int a, int b) { return a < b ? a : b; }
int max_v(int a, int b) { return a > b ? a : b; }
const int MAX_V = 1001;
int adj[MAX_V];
stack<int> stk;
int sccId[MAX_V], discovered[MAX_V], sccCount, discCount, comp[MAX_V];
int scc(int u) {
	stk.push(u);
	int ret = discovered[u] = discCount;
	discCount++;

	int v = adj[u];
	if (discovered[v] == -1)
		ret = min_v(ret, scc(v));
	else if (sccId[v] == -1)
		ret = min_v(ret, discovered[v]);

	if (ret == discovered[u]) {
		while (1) {
			int t = stk.top();
			stk.pop();
			sccId[t] = sccCount;
			comp[sccCount]++;
			if (t == u) break;
		}
		sccCount++;
	}
	return ret;
}

int sccadj[MAX_V];
int find(int u) {
	if (sccadj[u] == u) return u;
	return sccadj[u] = find(sccadj[u]);
}

int main() {
	int n, k, u, v, i, j, cyc, cmm[MAX_V][2] = {},limit=0;
	bool dp[MAX_V] = {};

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%d", &adj[i]);
		adj[i]--;
	}
	memset(sccId, -1, sizeof sccId);
	memset(discovered, -1, sizeof discovered);
	memset(sccadj, -1, sizeof sccadj);

	// SCC
	for (u = 0; u < n; u++)
		if (discovered[u] == -1) scc(u);

	// DAG
	for (u = 0; u < n; u++) {
		v = adj[u];
		sccadj[sccId[u]] = sccId[v];
	}

	set<int> components;

	// DSU
	for (i = 0; i < sccCount; i++) {
		cyc = find(i);
		components.insert(cyc);
		cmm[cyc][0] = comp[cyc]; // cmin
		cmm[cyc][1] += comp[i]; // cmax
	}
	dp[0] = 1;
	for (auto it = components.begin(); it != components.end(); it++) {
		for (i = limit; i >= 0; i--)
			if (dp[i]) {
				for (j = cmm[*it][0]; i + j <= k && j <= cmm[*it][1]; j++) {
					dp[i + j] = 1;
				}
			}
		limit += cmm[*it][1];
		limit = min_v(limit, k);
	}

	for (i = k; i>0; i--) 
		if (dp[i]) break;
	printf("%d", i);
	return 0;
}

  1-6. 축구 전술 (https://www.acmicpc.net/problem/3977)

     [분류 - SCC/ Topological sort]

    전형적인 SCC 문제가 되시겠다. 모든 SCC를 찾아서 진입 차수가 0인 SCC가 반드시 하나이면 된다. 그리고 출력은 SCC 내부에 있는 정점을 출력해주면 된다.

- 코드

#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
int min_v(int a, int b) { return a < b ? a : b; }
const int MAX_V = 100001;
vector<vector<int>> adj;
int sccId[MAX_V], discovered[MAX_V], sccCount, discCount;
stack<int> stk;
int scc(int u) {
	int ret = discovered[u] = discCount;
	discCount++;
	stk.push(u);

	for (int& v : adj[u]) {
		if (discovered[v] == -1)
			ret = min_v(ret, scc(v));
		else if(sccId[v] == -1)
			ret = min_v(ret, discovered[v]);
	}

	if (ret == discovered[u]) {
		while (1) {
			int t = stk.top(); stk.pop();
			sccId[t] = sccCount;
			if (t == u) break;
		}
		sccCount++;
	}
	return ret;
}

int main() {
	int T, N, M, A, B, i, ind[MAX_V], f, startSccCnt;
	bool confirm[MAX_V];
	scanf("%d", &T);
	while (T--) {
		vector<int> ans;
		scanf("%d%d", &N, &M);
		adj.clear();
		adj.resize(N);

		sccCount = discCount = 0;
		memset(sccId, -1, sizeof sccId);
		memset(discovered, -1, sizeof discovered);
		memset(ind, 0, sizeof ind);

		while (M--) {
			scanf("%d%d", &A, &B);
			adj[A].push_back(B);
		}
		for (i = 0; i < N; i++)
			if (discovered[i] == -1) scc(i);
		
		for (i = 0; i < N; i++) {
			for (int& v : adj[i])
				if (sccId[i] != sccId[v])
					ind[sccId[v]]++;
		}
		f = 1, startSccCnt = 0;
		memset(confirm, 0, sizeof confirm);
		for(i=0;i<N;i++)
			if (!ind[sccId[i]]) {
				f = 0;
				ans.push_back(i);
				if (!confirm[sccId[i]]) {
					confirm[sccId[i]] = 1;
					startSccCnt++;
				}
			}
		if (f || startSccCnt > 1) printf("Confused\n");
		else {
			for (int& a : ans) printf("%d\n", a);
		}
		puts("");
	}
	return 0;
}