Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
拓扑排序第一题,顺便也熟悉了一下图的储存,一次0ms AC//poj2367 //拓扑排序+图的储存 #include<cstdio> #include<queue> #include<vector> #include<string.h> using namespace std; int vis[105],can[105]; int main() { int n,i,num,a; int s[105]; while(scanf("%d",&n)!=EOF) { vector<int> g[105]; queue<int> q; num=-1; memset(vis,0,sizeof(vis)); memset(can,0,sizeof(can)); for(i=1;i<=n;i++) { while(scanf("%d",&a),a) { g[i].push_back(a); vis[a]++; } } for(i=1;i<=n;i++) { if(!vis[i]) { q.push(i); break; } } while(!q.empty()) { s[++num]=q.front(); can[s[num]]=1; q.pop(); for(i=0;i<g[s[num]].size();i++) vis[g[s[num]][i]]--; for(i=1;i<=n;i++) { if(!vis[i] && !can[i]) { q.push(i); break; } } } for(i=0;i<=num;i++) printf("%d ",s[i]); printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator