데이터 구조 총화 의 토폴로지 정렬
5506 단어 토폴로지 정렬
#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)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[APIO2009] 스윕 계획(강연통 컴포넌트+축소점+토폴로지 정렬+dp)제목: 지정된 시작점에서 시작하여 임의의 지정된 끝점까지 멈추는 지향도를 지정하여 지나간 모든 결점의 최대 점권과포인트, 모서리 수<=500000 하나의 강연통분량 내의 점은 서로 도달할 수 있기 때문에 그 중의 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.