3047: 【普及+/提高】【P1347】排序

$2\le n\le 26,1\le m\le 600$。

一、思路分析

1、不停的接收结点关系，创建有向图，A->B有边表示 A<B
2、每进入一个结点关系后，判断现在的有向图是否有环，有环就是冲突，提示并退出。判断是否有环可以用拓扑排序，
判断方法是：只要入队（或者出队）的次数不等于节点的个数，就说明有环，有环就是存在矛盾的。
3、在无环的情况下，找到入度为0的点，就是起始点，然后从起始点出发，bfs，看看能不能走出n步，如果能，就是完成了排序工作

二、理解与感悟

1、拓扑排序可以判断有没有环。
2、有环就是表示有循环比大小，就是有冲突。
3、拓扑排序要不断修改入度数组，如果入度数组需要不断建边继续使用，需要复制出来一份才能边建边、边检查拓扑序。
4、单个字符转字符串的办法最好用的是常量字符串ABCDEFGHIJKLMNOPQRSTUVWXYZ的substr

#include <bits/stdc++.h>

using namespace std;
const int N = 30;   //26个结点是极限

int in[N];          //入度数组
int tmp[N];      //入度临时操作数组
int n;              //表示需要排序的元素数量
int m;              //表示将给出的形如 A<B 的关系的数量
bool st[N];         //是否使用过

//实在想不出好主意了,用数字转为字符，再拼接到字符串，现在看来最好的办法就是写成一个常量字符串，然后substr去截取
string chr = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

struct Node {
    int n;
    string path;
};
//邻接表
vector<int> edge[N];

//拓扑排序，检查是否存在环，有环就是存在矛盾
bool topSort() {
    //清空状态数组
    memset(st, 0, sizeof st);
    queue<int> q;       //拓扑排序用的队列
    int sum = 0;//入队列数量
    //判断现在是不是有环，有环则退出。入度为0的结点入队列，进行拓扑排序
    for (int j = 1; j <= n; j++) if (!tmp[j]) q.push(j);
    //拓扑排序
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        sum++;
        //不是环中结点
        st[ u ] = true;
        //遍历每条出边
        for(auto c:edge[ u ]){
            if (!--tmp[c]) q.push(c);//在删除掉当前结点带来的入度后，是不是入度为0了，如果是将点y入队列
        }
    }
    //存在没进过队列的结点，存在表示有环。
    return sum < n;
}

int main() {
    //读入结点数和边数
    cin >> n >> m;

    //读入关系，建图，边建图边判断
    for (int i = 1; i <= m; i++) {
        string input;
        cin >> input;
        char x = input[0], y = input[2];//input[1]='<' 这个是死的，没用

        //建图
        int a = x - 'A' + 1, b = y - 'A' + 1;
        edge[a].push_back(b);//建立单边有向图,描述a<b
        in[ b ]++;    //入度数组++
        /*****下面的代码是拓扑排序的内容*******************************************************/
        //入度数组复制出来一份,因为拓扑排序需要不断的更改入度数组值，后面还需要原始的入度数组，所以需要复制出来一份。
        memcpy(tmp, in, sizeof in);
        bool existCircle = topSort();
        if (existCircle) {
            printf("Inconsistency found after %d relations.", i);
            exit(0);
        }
        /*****拓扑排序结束*********************************************************************/

        //到这里应该是无环
        //从入度为0的点出发，bfs看看是不是能走完n步，走完说明可以确定所有结点的大小关系，确定了就结束
        int cnt = 0;
        int startNode;
        for (int j = 1; j <= n; j++) if (!in[j]) startNode = j, cnt++;
        if (cnt > 1) continue; //存在两个及以上入度为零的点，是无法确定先后顺序的,需要继续读入关系数据

        //从startNode出发，看看能不能走出去n轮，如果能，就是可以确定所有结点的顺序，如果不能，就需要继续录入关系才能确定
        string path;
        queue<Node> q;
        q.push({startNode, chr.substr(startNode - 1, 1)});

        //清空状态数组，准备再战!
        memset(st, 0, sizeof st);
        while (!q.empty()) {
            Node u = q.front();
            q.pop();
            st[ u.n ] = true;
            if (u.path.size() > path.size())path = u.path;
            //遍历每条出边
            for (auto c:edge[ u.n ])
                q.push({c, u.path + chr.substr(c - 1, 1)});
        }
        //如果还存在没访问到的结点，那么就是无法完成排序,需要继续录入关系
        if (path.size() < n) continue;
        //输出路径
        printf("Sorted sequence determined after %d relations: %s.", i, path.c_str());
        exit(0);
    }
    //到达这里说明最终还没有确定下来所有结点关系，提示无法确定。
    printf("Sorted sequence cannot be determined.");
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define MAXN 30
int n,m,a,b,ans[MAXN],outd[MAXN],ind[MAXN];
bool u[MAXN];
vector <int> p[MAXN];
string ss,st;
struct node {
	int x,d;
};
string get_sequence(int tail) {
	string ret;
	if (ans[tail] == 0) {
		ret +=(tail - 1 + 'A');
		return ret;
	}
	else {
		 ret +=(tail - 1 + 'A');
		 return get_sequence(ans[tail]) + ret;
	}
}
int check() {
	queue <node> q;
	int cnt=0, tot_nodes = 0; 
	memset(ans,-1,sizeof(ans));
	for (int i = 1; i <= n; i++) {
		if (u[i] && ind[i] == 0) {
			q.push((node){i,1});
			ans[i] = 0;
		}
		if (u[i]) tot_nodes++;
    }
    int maxa=1;
    int t_ind[MAXN]={0};
 	for (int i = 1; i <= n; i++) {
		t_ind[i]=ind[i];
    }
    while (!q.empty()) {
    	node t=q.front();
    	q.pop();
    	cnt++;
    	if (outd[t.x] == 0) {
    		maxa=max(maxa,t.d);
    		if (maxa == n) {
		        ss=get_sequence(t.x);
		        return 1;    			
			}
		}
		for (int i = 0, sz = p[t.x].size(); i < sz ;i++) { 
			t_ind[p[t.x][i]]--;
			if (t_ind[p[t.x][i]] == 0) {
			 	ans[p[t.x][i]] = t.x;
			 	q.push((node){p[t.x][i],t.d+1});
			}
		}
	}
	if (cnt != tot_nodes) return 2;
	else return 0;
}
int main(){
    cin >> n >> m; 
    for (int i = 1; i <= m ; i++) {
    	cin >> st;
    	a=st[0]-'A' + 1;b=st[2]-'A' + 1;
		u[ a ] = true; u[ b ] = true;
		outd[ a ]++;ind[ b ]++;
		p[ a ].push_back(b);    	
    	if (check() == 2) {
    		printf("Inconsistency found after %d relations.",i);
    		return 0;
    	}else if (check() == 1) {
    		cout << "Sorted sequence determined after " << i <<" relations: ";
    		cout << ss <<".";
    		return 0;
		}
	}
	cout << "Sorted sequence cannot be determined.";
	return 0;
}