首页 > 代码库 > ACM2647拓扑排序逆运算

ACM2647拓扑排序逆运算

2024-07-14 20:02:29   223人阅读

2647题是对工人排序问题，不是从头到尾排序，而是从尾到头排序；

代码中用到vector和queue容器，权当练习。

用广搜进行拓扑排序的逆运算。

 1 #include<iostream> 2 #include<vector> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 const int maxn=10010; 7 int main() 8 { 9     int n,m;10     int sum[maxn];11     int out[maxn];12     while(cin>>n>>m)13     {14         int a,b;15         vector<int>next[maxn];16         queue<int>q;17         memset(sum,0,sizeof(sum));18         memset(out,0,sizeof(out));19         for(int i=0;i<m;i++)20         {21             cin>>a>>b;22             next[b].push_back(a);23             out[a]++;24         }25         for(int i=1;i<=n;i++)26         {27             if(out[i]==0)28             {29                 q.push(i);30                 sum[i]=888;31             }32         }33         if(q.empty())34         {35             cout<<-1<<endl;36             continue;37         }38         int cnt=n;39         while(!q.empty())40         {41             int v=q.front();42             q.pop();43             cnt--;44             for(int i=0;i<next[v].size();i++)45             {46                 out[next[v][i]]--;47                 if(out[next[v][i]]==0)48                 {49                     q.push(next[v][i]);50                     sum[next[v][i]]=sum[v]+1;51                 }52             }53         }54         if(cnt>0)55         {56             cout<<-1<<endl;57             continue;58         }59         int ans=0;60         for(int i=1;i<=n;i++)61         {62             ans+=sum[i];63         }64         cout<<ans<<endl;65     }66     return 0;67 }

 


联系
我们