글 읽기 - dfs로해서 맞긴 했는데 궁금한 점이 있습니다.

jangyoqr 5년 전 0

시간이 너무 많이 나온 것 같습니다. 혹시 개선 해야 한다면 어느 부분을 손대는게 좋을까요? 그리고 하나 더 dfs 방법말고 다른 방법으로 하는게 더 빠른가요??

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
/*****************/

using namespace std;
vector<int>vertex[32001];
vector<int> ans;
int indegree[32001];
int check[32001] = { 0 };
void dfs(int n) {
	check[n] = 1;
	for (int k = 0; k < vertex[n].size(); k++) {
		int next = vertex[n][k];
		if (check[next] == 0) {
			dfs(next);
		}
	}
	ans.push_back(n);
	
}
int main()
{
	int n, m,a,b;


	cin >> n >> m;
	while (m--) {
		scanf("%d %d", &a, &b);
		vertex[a].push_back(b);
		indegree[b]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if(indegree[i]==0)
		dfs(i);
	}
	for (int i = ans.size() - 1; i >= 0; i--) printf("%d ",ans[i]);
	
}

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

문제

문제

출처

ICPC

dfs로해서 맞긴 했는데 궁금한 점이 있습니다.

jangyoqr 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말