|
#include <iostream> #include <vector> #include <queue> #include <cstring> #define MAX 1005 using namespace std; ///前向星存儲結(jié)構(gòu)，下標(biāo)從0開始 struct GraphQX{ vector<int> to;///當(dāng)前邊指向的點 vector<int>pre;///當(dāng)前邊的前一條邊 vector<int>info;///當(dāng)前點指向的最后一條邊 int zroENode;///有意義的0邊的起始點 GraphQX(int eSize = 0, int nSize = 0){ to.resize(eSize); info.resize(nSize); pre.resize(eSize); zroENode = - 1; } void expan(int i){ if(info.size() < i + 1) info.resize(i + 1); } //增加a, b邊; void addEdge(int a, int b){ expan(a); expan(b); to.push_back(b); pre.push_back(info[a]); info[a] = to.size() - 1; if(info[a] == 0)//0邊上的起始點，其他0邊上的起始點不是真正的起點,遇到0邊可以直接退出 zroENode = a; } //刪除最后一條邊 void deletLastEdge(){ for(int i = 0; i < info.size(); i++){ if(info[i] == to.size() - 1){ info[i] = pre.back(); break; } } pre.pop_back(); to.pop_back(); } //清空 void clear(){ info.clear(); pre.clear(); to.clear(); zroENode = -1; } }; GraphQX qx; int Num; int du[MAX]; vector<int>ans; void bfs( ){ queue<int>q; for(int i = 0; i < Num; i++){ if(du[i] == 0){ q.push(i); } } while(!q.empty()){ int u = q.front(), v; q.pop(); ans.push_back(u + 1); if(u < qx.info.size()){//判斷越界,邊對應(yīng)的點相對小的情況就會越界 int e = qx.info[u]; while(e){ v = qx.to[e]; du[v]--; if(du[v] == 0)q.push(v); e = qx.pre[e]; } if( u == qx.zroENode && qx.zroENode != -1){ v = qx.to[0]; du[v]--; if(du[v] == 0)q.push(v); } } } for(int i = 0; i < ans.size() - 1; i++){ cout<<ans[i]<<" "; }cout<<ans.back()<<endl; } int main() { ///freopen("in.txt","w",stdout); cin>>Num; //while(){ int a; ans.clear(); qx.clear(); memset(du, 0, sizeof(du)); for(int i = 0; i < Num; i++){ while(cin>>a, a != 0){ qx.addEdge(i, a - 1); du[a - 1]++; } } bfs(); //} } |
|
|
來自： 昵稱13014912 > 《圖論》
