Source Code
Problem: 2367 User: fan1913068672Memory: 276K Time: 16MSLanguage: C++ Result: Accepted Source Code #include"iostream" #include"stack" #include"vector" #include"cstdio" using namespace std; vector< vector<int> > G;//采用邻接表保存图 vector<int> degree; //度数表 vector<int> is_in_stack;//判断是否入过栈 vector<int> ans; //保存答案 int n,m; //点数 弧数 int topo_sort(){ stack<int> st; for(int i=1;i<=n;i++){ //先找到入度为0的点 压入栈中 if(degree[i]==0){ st.push(i); is_in_stack[i] = 1; //更新点的标志 } } while(!st.empty()){ int now = st.top();st.pop(); ans.push_back(now); for(int i=0;i<G[now].size();i++){//把邻接的点的度数更新 degree[G[now][i]]--; } for(int i=1;i<=n;i++){ if(degree[i]==0&&!is_in_stack[i]){//把更新之后的图中入度为0的点入栈 st.push(i); is_in_stack[i]=1; } } } } int main(){ while(cin>>n){ G.resize(n+1); is_in_stack.resize(n+1); degree.resize(n+1); for(int i=1;i<=n;i++){ int ed; while(scanf("%d",&ed)&&ed){ G[i].push_back(ed); } } for(int i=1;i<=n;i++){ is_in_stack[i]=0; for(int j=0;j<G[i].size();j++){ degree[G[i][j]]++; } } topo_sort(); int first = 1; for(int i=0;i<ans.size();i++){ if(first) {first = 0;cout<<ans[i];} //else cout<<"--->"<<ans[i]; else cout<<" "<<ans[i]; } cout<<endl; } return 0; }