DFS 구현 토폴로지 정렬, 시간 복잡도(V 회차 반복 + E 회차)

1645 단어 DFS拓扑排序

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;
}

 
 
류여가의 코드도 참고할 수 있다.

좋은 웹페이지 즐겨찾기