DFS 구현 토폴로지 정렬, 시간 복잡도(V 회차 반복 + E 회차)
Ordering Tasks
UVA-10305 아래 코드는 이 문제의 문제입니다.
// dfs , V E , V ,E
#include
#include
#include
#include
using namespace std;
#define Maxn 110
int n,m,G[Maxn][Maxn],vis[Maxn],res[Maxn],p;
bool dfs(int u) {
for(int i = 1 ; i <= n ; ++i) {
if(G[u][i]) {
if(vis[i] == -1) return false; // i dfs
else if(!vis[i]) { // ,
vis[i] = -1;
if(!dfs(i)) return false;
else res[p--] = i;
}
vis[i] = 1;
}
}
return true;
}
int main(void)
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while(cin >> n >> m) {
if(n == 0 && m == 0) break;
int tmp,tp;
memset(G,0,sizeof(G));
memset(vis,0,sizeof(vis));
memset(res,0,sizeof(res));
for(int i = 1; i <= m ; ++i) {
cin >> tmp >> tp;
G[tmp][tp] = 1;
}
p = n;
for(int i = 1 ; i <= n ; ++i) {
if(vis[i] == 1) continue;
vis[i] = -1; // -1 dfs
if(dfs(i)) res[p--] = i; // ,dfs
else cout << " " << endl;
vis[i] = 1;
}
for(int i = 1; i <= n; ++i) {
cout << res[i];
if(i != n) cout << " "; else cout << endl;
}
}
return 0;
}
류여가의 코드도 참고할 수 있다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ] 5568 카드 놓기아이디어 Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고 sb에 고른 카드를 담도록 하였다. 이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.