1 条题解
-
-2
#include <bits/stdc++.h> #define MAXN 50 using namespace std; int n,m; struct Node{ int u; int val; Node(int u=0,int val=0):u(u),val(val){} }; vector<int> vec[MAXN]; int ru[MAXN]; int sum; int ans; int k; set<int> s1; void make(){ queue<int> q; int ru1[MAXN]; memset(ru1,0,sizeof(ru1)); for(int i=0; i<26; i++){ for(int j=0; j<vec[i].size(); j++){ ru1[vec[i][j]]++; } } for(int i=0; i<26; i++){ if(ru1[i]==0&&s1.count(i)){ q.push(i); cout<<char(i+'A'); } } while(!q.empty()){ int u=q.front(); q.pop(); for(int i=0; i<vec[u].size(); i++){ int v=vec[u][i]; ru1[v]--; if(ru1[v]==0){ q.push(v); cout<<char(v+'A'); } } } } int have; void topo(){ queue<Node> q; for(int i=0; i<26; i++){ if(ru[i]==0&&s1.count(i)){ q.push(Node(i,1)); sum++; } } while(!q.empty()){ int u=q.front().u; int val=q.front().val; q.pop(); for(int i=0; i<vec[u].size(); i++){ int v=vec[u][i]; ru[v]--; if(ru[v]==0){ sum++; q.push(Node(v,val+1)); ans=max(ans,val+1); } } } if(ans==n){ printf("Sorted sequence determined after %d relations: ",k); make(); cout<<"."; exit(0); } if(sum!=have){ printf("Inconsistency found after %d relations.",k); exit(0); } } int ru2[MAXN]; int main(){ cin>>n>>m; for(int i=1; i<=m; i++){ string s; cin>>s; k=i; vec[s[0]-'A'].push_back(s[2]-'A'); s1.insert(s[0]-'A'); s1.insert(s[2]-'A'); have=s1.size(); ru2[s[2]-'A']++; sum=0; ans=0; memcpy(ru,ru2,sizeof(ru2)); topo(); } printf("Sorted sequence cannot be determined."); return 0; }
- 1
信息
- ID
- 348
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 10
- 已通过
- 5
- 上传者