P1347 排序
题目传送门
一、思路分析
1、不停的接收结点关系，创建有向图，A->B有边表示 A
判断方法是：只要入队（或者出队）的次数不等于节点的个数，就说明有环，有环就是存在矛盾的。
3、在无环的情况下，找到入度为0的点，就是起始点，然后从起始点出发，bfs，看看能不能走出n步，如果能，就是完成了排序工作
二、理解与感悟
1、拓扑排序可以判断有没有环。
2、有环就是表示有循环比大小，就是有冲突。
3、拓扑排序要不断修改入度数组，如果入度数组需要不断建边继续使用，需要复制出来一份才能边建边、边检查拓扑序。
4、单个字符转字符串的办法最好用的是常量字符串\(ABCDEFGHIJKLMNOPQRSTUVWXYZ\)的\(substr\),其它的花里胡哨的不好用，背模板吧。
三、邻接表解法
#include
using namespace std;
const int N = 30; //26个结点是极限
int in[N]; //入度数组
int tmp[N]; //入度临时操作数组
int n; //表示需要排序的元素数量
int m; //表示将给出的形如 A edge[N];
//拓扑排序，检查是否存在环，有环就是存在矛盾
bool topSort() {
//清空状态数组
memset(st, 0, sizeof st);
queue 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 1) continue; //存在两个及以上入度为零的点，是无法确定先后顺序的,需要继续读入关系数据
//从startNode出发，看看能不能走出去n轮，如果能，就是可以确定所有结点的顺序，如果不能，就需要继续录入关系才能确定
string path;
queue 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
using namespace std;
const int N = 30; //26个结点是极限
const int M = 610; //600条边是极限
int in[N]; //入度数组
int tmp[N]; //入度临时操作数组
int n; //表示需要排序的元素数量
int m; //表示将给出的形如 A 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 (int j = head[u]; j; j = edge[j].next) {
int y = edge[j].to;
if (!--tmp[y]) q.push(y);//在删除掉当前结点带来的入度后，是不是入度为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;
add(a, b); //建立单边有向图,描述a 1) continue; //存在两个及以上入度为零的点，是无法确定先后顺序的,需要继续读入关系数据
//从startNode出发，看看能不能走出去n轮，如果能，就是可以确定所有结点的顺序，如果不能，就需要继续录入关系才能确定
string path;
queue 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 (int j = head[u.n]; j; j = edge[j].next) {
int y = edge[j].to;
q.push({y, u.path + chr.substr(y - 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;
}