若根据前 x 个关系即可确定这 n 个元素的顺序 yyy..y(如 ABC), 输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前 x 个关系即发现存在矛盾 (如 A<B,B<C,C<A), 输出
Inconsistency found after 2 relations.
若根据这 m 个关系无法确定这 n 个元素的顺序, 输出
Sorted sequence cannot be determined.
(提示: 确定 n 个元素的顺序后即可结束程序, 可以不用考虑确定顺序之后出现矛盾的情况)
方法:
判环: 拓排时记录 indegree==0 的节点数, 若小于当时含有的总节点数, 则有环.
判定成功: 层数 ==n.
- Code:
- #include <bits/stdc++.h>
- # define LL long long
- using namespace std;
- const int maxn=27;
- int n,m;
- vector<int> adj[maxn];
- int ind[maxn];
- int tmpind[maxn];
- set<int> have;
- int level[maxn];
- bool hascycle;
- bool complete;
- void print(){
- queue<int> q;
- int ind1[maxn];
- for(int i=0;i<26;++i){
- ind1[i]=ind[i];
- }
- for(int i=0;i<26;++i){
- if(have.find(i)!=have.end() && ind1[i]==0){
- q.push(i);
- char c='A'+i;
- printf("%c", c);
- break;
- }
- }
- while(!q.empty()){
- int u=q.front();
- q.pop();
- for(int i=0;i<adj[u].size();++i){
- int v=adj[u][i];
- --ind1[v];
- if(ind1[v]==0){
- char c='A'+v;
- printf("%c", c);
- q.push(v);
- }
- }
- }
- }
- void topo(){
- for(int i=0;i<26;++i){
- tmpind[i]=ind[i];
- }
- memset(level,0,sizeof(level));
- int maxlevel=0;
- int cnt=0;
- queue<int> q;
- for(int i=0;i<26;++i){
- if(have.find(i)!=have.end() && tmpind[i]==0){
- q.push(i);
- cnt++;
- level[i]=1;
- }
- }
- while(!q.empty()){
- int u=q.front();
- q.pop();
- for(int i=0;i<adj[u].size();++i){
- int v=adj[u][i];
- --tmpind[v];
- level[v]=max(level[v],1+level[u]);
- maxlevel=max(maxlevel,level[v]);
- if(tmpind[v]==0){
- cnt++;
- q.push(v);
- }
- }
- }
- if(cnt!=have.size()){
- hascycle=true;
- return;
- }
- if(maxlevel==n){
- complete=true;
- return;
- }
- }
- int main(){
- scanf("%d %d", &n, &m);
- hascycle=false;
- complete=false;
- for(int i=1;i<=m;++i){
- string s;
- cin>>s;
- int u=s[0]-'A';
- int v=s[2]-'A';
- have.insert(u);
- have.insert(v);
- adj[u].push_back(v);
- ind[v]++;
- topo();
- if(hascycle){
- printf("Inconsistency found after %d relations.", i);
- return 0;
- }
- if(complete){
- printf("Sorted sequence determined after %d relations:",i);
- print();
- printf(".");
- return 0;
- }
- }
- printf("Sorted sequence cannot be determined.");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3399738.html