글 읽기 - 맞추긴 했는데요.. 위상정렬 기초 질문입니다.

h575h 5년 전 0

소스코드에 dfs_all() 함수 부분의 주석 처리된 부분이 그래프가 DAG인지 아닌지를 검사하는 부분인데요,

이 부분 때문에 시간 초과가 나지만 문제의 조건에 모순이 되면(DAG가 아니면) 어떡하라는 조건이 없기 때문에

모든 입력이 DAG일 것이므로 주석부분이 없어도 정답이 됩니다.

실제로 시간 초과가 나지 않게 DAG 검사를 하려면 어떻게 짜야할까요.....?

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)

void dfs(vector<list<int>>& adj, vector<bool>& visited, vector<int>& sorted, int here)
{
	visited[here] = true;
	for (list<int>::iterator it = adj[here].begin(); it != adj[here].end(); it++)
	{
		int there = *it;
		if (!visited[there])
			dfs(adj, visited, sorted, there);
	}
	sorted.push_back(here);
}

vector<int> dfs_all(vector<list<int>>& adj)
{
	vector<bool> visited(adj.size(), false);
	vector<int> sorted;

	for (int here = 0; here < adj.size(); here++)
		if (!visited[here]) dfs(adj, visited, sorted, here);
	
	reverse(sorted.begin(), sorted.end());

	//for (int n = 0; n < adj.size(); n++)
	//	for (int m = n + 1; m < adj.size(); m++)
	//		for (list<int>::iterator it = adj[sorted[m]].begin(); it != adj[sorted[m]].end(); it++)
	//			if (*it == sorted[n]) return vector<int>();

	return sorted;
}

int main()
{
	cin.tie(NULL);
	cout.sync_with_stdio(false);
	int N, M, A, B;
	/*****************/
	// (문제)
	// 줄 세우기(2252)
	// (입력)
	// N: 학생의 수(1<=N<=32,000)
	// M: 키를 비교한 횟수(1<=M<=100,000)
	// A, B: 두 학생의 번호, A의 키가 B보다 작다(A가 B보다 앞에 선다)
	// (출력)
	// 학생들의 줄을 세운 결과. 답이 여러 가지면 아무거나 출력
	// (알고리즘 분류)
	// 위상 정렬, 우선 순위 큐
	// (풀이)
	// 
	/*****************/
	cin >> N >> M;
	vector<list<int>> adj(N);
	for (int m = 0; m < M; m++)
	{
		cin >> A >> B;
		adj[A - 1].push_back(B - 1);
	}
	vector<int> sorted = dfs_all(adj);

	for (int n = 0; n < N; n++)
	{
		cout << sorted[n]+1;
		if (n != N - 1) cout << ' ';
	}

	return 0;
}

Green55 5년 전 5

DFS를 하면서 사이클을 탐지하는 방법이 있습니다.

위의 코드에서, DFS(i)라는 함수가 끝나기 전에 경로를 타고 i를 한번 더 방문 할 수 있다면 사이클이 있다는 뜻입니다.

bool finish[] = {false로 초기화};
DFS(int here){
    visit[here] = true;
    for(there = {here에 연결된 모든 정점}){
        if(visit[there] == false)
            DFS(there);
        if(visit[there] == true && finish[there] == false) 
            사이클이 존재
    }
    finish[here] = true;
}

h575h 5년 전 0

해결했습니다 감사합니다!

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

문제

문제

출처

ICPC

맞추긴 했는데요.. 위상정렬 기초 질문입니다.

h575h 5년 전 0

Green55 5년 전 5

h575h 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말