데이터 구조 총화 의 토폴로지 정렬

5506 단어 토폴로지 정렬
1. 링 없 는 그림 이 있 습 니 다. 출력 요 구 는 다음 과 같 습 니 다. 앞의 노드 는 다음 노드 를 직접 또는 간접 적 으로 가 리 켜 야 합 니 다.
#include 
#include 
#include 
#include 
#include 
using namespace std;
class G
{
    int v;
    list<int> *adj;
    void topological_Sort_Util(int v,bool visited[],stack<int> &Stack);
public:
    G(int v);
    void addedge(int v,int w);
    void topological_Sort();
};
G::G(int v)
{
    this->v=v;
    adj=new list<int>[v];
}
void G::addedge(int v,int w)
{
    adj[v].push_back(w);
}
void G::topological_Sort_Util(int v,bool visited[],stack<int> &Stack)
{
    visited[v]=true;
    list<int>::iterator i;
    for(i=adj[v].begin();i!=adj[v].end();++i)
        if(!visited[*i]) topological_Sort_Util(*i,visited,Stack);
    Stack.push(v);
}
void G::topological_Sort()
{
    stack<int> Stack;
    bool *visited=new bool[v];
    memset(visited,0,sizeof(visited));
    for(int i=0;iif(visited[i]==false)
        topological_Sort_Util(i,visited,Stack);
        int t=0;
    while(!Stack.empty())
    {
        int tmp=Stack.top();
        if(tmp && t!=0)
        cout<<" "<else if(tmp && t==0)
            cout<cout<int main()
{
   //freopen("debug\\in.txt","r",stdin);
    //freopen("debug\\out.txt","w",stdout);
    int m,n;
    while(cin>>n>>m && !(n==0 && m==0))
    {
        if(m==0)
        {
            for(int i=1;i<=n;i++)
            {
                if(i==1) cout<else cout<<" "<cout<else
        {
            G g(n+1);
        int a,b;
        for(int i=0;icin>>a>>b;
             g.addedge(a,b);
        }
         g.topological_Sort();
        }

    }

    return 0;
}
/*
5 4
1 2
2 3
1 3
1 5
0 0
1 4 2 5 3(Special Judge)

좋은 웹페이지 즐겨찾기