글 읽기 - 2150번 Strongly Connected Component 뭐가 틀린걸까요?

gkfkagkfka12 6년 전 0

Kosaraju's algorithm을 써서 그대로 구현했습니다.

1. 기존 그래프에 대해 DFS돌려서 finish time 구하기

2. 기존 그래래프를 transponse 한 그래프 구하기

3. transpose한 그래프에 대해 finish time 내림차순으로 DFS 돌려서 SCC 계산하기

문제의 예제가 1개 밖에 없어서 구글링해서 SCC들을 여러개 찾은 후 돌려봤는데도 맞습니다.

꽤 복잡한 그래프로 했는데도 맞는데 뭐가 문제일까요?

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

struct fv {
	int finish_time;
	int vertex;
};

std::vector<int> graph[10001];
std::vector<int> graphT[10001];
std::vector<std::vector<int>> SCC;
fv finish[10001];

bool visited[10001];
int visitNum = 0;

// graph의 모든 vertex를 검사하는데 vertex A에 B,C,D가 연결되었다면
// B,C,D에 A가 연결되도록 Transpose 시킨다.
void Transpose(int vertexNum)
{
	for (int i = 1; i <= vertexNum; i++) {
		for (int j = 0; j < graph[i].size(); j++) {
			graphT[graph[i][j]].push_back(i);
		}
	}
}

void Print(std::vector<int> g[], int vertexNum)
{
	for (int i = 1; i <= vertexNum; i++) {
		printf("%d : ", i);
		for (int j = 0; j < g[i].size(); j++) {
			printf("%d ", g[i][j]);
		}
		printf("\n");
	}
}

void DFS(int s, std::vector<int> g[], bool transpose)
{
	// 방문한 vertex면 DFS이미 한 vertex임.
	// DFS의 시작 vertex와 상관없이 하게 하기 위함
	if (visited[s]) return;

	std::stack<int> adj;
	// 인접한 vertex있는지 검사하는 flag
	bool isAdjacent = false;
	std::vector<int> temp;
	adj.push(s);
	visited[s] = true;
	
	while (!adj.empty()) {
		int v = adj.top();
		// 방문하지 않았고, transpose가 아닐 경우에만 필요함.
		if (!visited[v] && !transpose) visitNum++;

		// 인접한 vertices 검사
		// 방문하지 않았을 경우 방문하고 스택에 넣은다음 isAdjacent를 true로 해서 방문했다고 표시
		for (int i = 0; i < g[v].size(); i++) {
			if (!visited[g[v][i]]) {
				visited[g[v][i]] = true; 
				adj.push(g[v][i]);
				isAdjacent = true;
			}
		}

		// 인접한 vertex가 없으면 스택에서 pop하고 끝날 때마다 해당 vertex의 finish 시간을 계산해준다.
		if (!isAdjacent) {
			adj.pop();
			// 방문하는 각 vertex를 SCC에 벡터로 집어넣기 위해
			// temp 벡터에 vertex를 집어넣는 것.
			if (transpose) temp.push_back(v);
			else {
				finish[v].finish_time = ++visitNum;
				finish[v].vertex = v;
			}		
		}
		isAdjacent = false;
	}
	// DFS를 한번 돌고 방문한 모든 vertices가 temp에 있으므로 그 벡터를 SCC 벡터에 넣는다.
	if(transpose) SCC.push_back(temp);
}

// finish 벡터를 정렬하기 위한 비교함수
bool cmp(const fv &lhs, const fv &rhs)
{
	return lhs.finish_time < rhs.finish_time;
}

// SCC 벡터(벡터의 벡터)를 정렬하기 위한 비교함수
bool cmp2(const std::vector<int>& lhs, const std::vector<int>& rhs)
{
	return lhs[0] < rhs[0];
}

int main(void)
{
	int v, e; scanf("%d %d", &v, &e);
	while (e--) {
		int v1, v2;
		scanf("%d %d", &v1, &v2);
		graph[v1].push_back(v2);
	}

	// 방문하지 않은 것으로 전부 초기화
	for (int i = 1; i <= v; i++) visited[i] = false;
	// 기존 그래프 G에 DFS 돌려서 finish time 계산
	for (int i = 1; i <= v; i++) DFS(i, graph,false);

	// finish time 내림차순으로 그래프 G의 vertex 정렬
	std::sort(finish + 1, finish + v + 1, cmp);

	// 기존 그래프 G로 transpose해서 graphT 생성.
	Transpose(v);

	// 방문배열 다시 사용해야 하니, 초기화하고 이번엔 Transpose 된
	// 그래프 graphT로 DFS돌려서 SCC 생성
	for (int i = 1; i <= v; i++) visited[i] = false; visitNum = 0;
	for (int i = v; i >= 1; i--) DFS(finish[i].vertex, graphT, true);

	//Print(graphT, v);

	for(int i=0; i<SCC.size(); i++) std::sort(SCC[i].begin(), SCC[i].end());
	std::sort(SCC.begin(), SCC.end(), cmp2);

	printf("%d\n", SCC.size());
	for (int i = 0; i < SCC.size(); i++) {
		for (int j = 0; j < SCC[i].size(); j++) printf("%d ", SCC[i][j]);
		printf("-1\n");
	}


	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2150번 Strongly Connected Component 뭐가 틀린걸까요?

gkfkagkfka12 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말