数据结构第12周 ：（ 有向无环图的拓扑排序 + 拓扑排序和关键路径 + 确定比赛名次 + 割点 ）

有向无环图的拓扑排序

【问题描述】

由某个集合上的一个偏序得到该集合上的一个全序，这个操作被称为拓扑排序。偏序和全序的定义分别如下：若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。设R是集合X上的偏序，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。由偏序定义得到拓扑有序的操作便是拓扑排序。

拓扑排序的流程如下：

1. 在有向图中选一个没有前驱的顶点并且输出之；

2. 从图中删除该顶点和所有以它为尾的弧。

重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
在本题中，读入一个有向图的邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法判断此图是否有回路，如果没有回路则输出拓扑有序的顶点序列。

【输入形式】

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。

以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个整数，如果为1，则表示第i个顶点有指向第j个顶点的有向边，0表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。

【输出形式】

如果读入的有向图含有回路，请输出“ERROR”，不包括引号。

如果读入的有向图不含有回路，请按照题目描述中的算法依次输出图的拓扑有序序列，每个整数后输出一个空格。

请注意行尾输出换行。

【样例输入】

4
0 1 0 0
0 0 1 0
0 0 0 0
0 0 1 0
【样例输出】

3 0 1 2

【说明】请注意采用邻接表存储结构时，链表创建需采用尾插法，以保证后续结点从小到大排列。

在本题中，需要严格的按照题目描述中的算法进行拓扑排序，并在排序的过程中将顶点依次储存下来，直到最终能够判定有向图中不包含回路之后，才能够进行输出。

另外，为了避免重复检测入度为零的顶点，可以通过一个栈结构维护当前处理过程中入度为零的顶点。

#include<iostream>
#include<stdlib.h>
#include<stack>
#define N 50
using namespace std;typedef struct node
{int data;struct node * next;
}ArcNode;typedef struct
{int in; //表示该节点的入度int vertex; // 该节点的信息int flag; //判断该节点是否入栈的标志ArcNode * firstedge;
}ALGraph;ALGraph G[N];
int res[N];void TopoSort(int limit)
{stack<ALGraph*> s;int count = 0;int i = 0;for(i = 0; i < limit; i ++){if(G[i].in == 0){s.push(&G[i]);G[i].flag = 0;}}while(!s.empty()){ALGraph * pos = s.top();s.pop();count ++;res[count] = pos->vertex;ArcNode * p = pos->firstedge;while(p != NULL){int num = p->data;G[num].in --;p = p->next;}for(i = 0 ; i <limit; i ++){if(G[i].in == 0 && G[i].flag == 1){s.push(&G[i]);G[i].flag = 0;}}}if(count == limit){for(i = 1; i <= limit; i ++){cout<<res[i]<<" ";}}else{cout<<"ERROR";}
}int main()
{int NodeNum = 0;cin>>NodeNum;int i = 0;int j = 0;for(i = 0; i < NodeNum; i ++) //邻接表初始化{G[i].in = 0;G[i].vertex = i;G[i].flag = 1;G[i].firstedge = NULL;}for(i = 0; i < NodeNum; i ++){for(j = 0; j < NodeNum; j ++){int num;cin>>num;if(num == 0) continue;else{ArcNode * temp = (ArcNode*)malloc(sizeof(ArcNode));temp->data = j;temp->next = NULL;ArcNode * pos = G[i].firstedge;while(1){if(pos == NULL) break;if(pos->next == NULL) break;elsepos = pos->next;}if(pos == NULL){G[i].firstedge = temp;}else{pos->next = temp;}G[j].in ++;}}}TopoSort(NodeNum);return 0;
}

拓扑排序和关键路径

【问题描述】若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网。如果用AOE网来表示一项工程，那么，仅仅考虑各个子工程之间的优先关系还不够，更多的是关心整个工程完成的最短时间是多少；哪些活动的延期将会影响整个工程的进度，而加速这些活动是否会提高整个工程的效率。因此，通常在AOE网中列出完成预定工程计划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间以及确定哪些活动是影响工程进度的关键。
【输入形式】第一行输入两个数字，分别表示顶点数和边数；从第二行开始，输入边的信息，格式为（i，j, weight）
【输出形式】关键路径的总时间（最大路径长度），代表关键活动的边，格式为（顶点1，顶点2），按大小顺序排列
【样例输入】
6 8
0 1 3
0 2 2
1 3 2
1 4 3
2 3 4
2 5 3
3 5 2
4 5 1
【样例输出】

8

0 2

2 3

3 5

#include<iostream>
#define N 50
#include<stack>
#include<stdlib.h>
using namespace std;typedef struct node
{int NodeId;int weight;int edgeId;struct node * next;
}ArcNode; //邻接结点结构体typedef struct
{int in;int out;int flag;int vertex;ArcNode * firstedge;
}ALGraph; //邻接表结构体ALGraph G[N];
int Relation[N][N];
int VE[N];
int VL[N];
int EE[N];
typedef struct
{int Weight;int node1;int node2;
}point;
point EL[N];
int el[N];
int count = -1;void MaxPathLen(int limit)
{int i = 0;stack<ALGraph*> S;//用入度来处理正向拓扑排序（填充VEfor(i = 0; i < limit; i ++){if(G[i].in == 0){S.push(&G[i]);G[i].flag = 0;}}while(!S.empty()){ALGraph * temp = S.top();S.pop();ArcNode * p = temp->firstedge;while(p != NULL) //弹出的节点的相邻节点的入度减一，填充VE{G[p->NodeId].in --;if(VE[temp->vertex] + p->weight > VE[p->NodeId]){VE[p->NodeId] = VE[temp->vertex] + p->weight;//cout<<p->NodeId<<" "<<VE[p->NodeId]<<endl;}p = p->next;}for(i = 0; i < limit; i ++){if(G[i].in == 0 && G[i].flag == 1){S.push(&G[i]);G[i].flag = 0;}}}for(i = 0; i < limit; i ++){G[i].flag = 1; //将标记初始化}int max = -1;int maxid = 0;for(i = 0; i < limit; i ++){if(VE[i] > max){max = VE[i];maxid = i;}}VL[maxid] = max;//用出度来处理逆向拓扑排序（填充VLfor(i = 0; i < limit; i ++){if(G[i].out == 0){S.push(&G[i]);G[i].flag = 0;}}while(!S.empty()){ALGraph * temp = S.top();S.pop();for(i = 0; i < limit; i ++){if(Relation[temp->vertex][i] == 1){G[i].out --;Relation[temp->vertex][i] = 0;ArcNode * pos = G[i].firstedge;while(pos->NodeId != temp->vertex) pos = pos->next;if(VL[i] == 0){VL[i] = VL[temp->vertex] - pos->weight;}if(VL[temp->vertex] - pos->weight < VL[i] ){VL[i] = VL[temp->vertex] - pos->weight;//cout<<temp->vertex<<" "<<VL[temp->vertex]<<" "<<pos->weight<<endl;}}}for(i = 0; i < limit; i ++){if(G[i].out == 0 && G[i].flag == 1){S.push(&G[i]);G[i].flag = 0;}}}//计算EE[N],EL[N]for(i = 0; i <= count; i ++){int e = EE[i];int l = EL[i].node2;EE[i] = VE[e];el[i] = VL[l] - EL[i].Weight;}cout<<max<<endl;for(i = 0; i <= count; i ++){if(EE[i] == el[i])cout<<EL[i].node1<<" "<<EL[i].node2<<endl;}
}int main()
{int NodeNum;int EdgeNum;cin>>NodeNum>>EdgeNum;int i, j;for(i = 0; i < NodeNum; i ++){VE[i] = 0;VL[i] = 0;}for(i = 0; i < EdgeNum; i ++){EE[i] = 0;el[i] = 0;EL[i].Weight = 0;EL[i].node1 = 0;EL[i].node2 = 0;}for(i = 0; i < NodeNum; i ++) //表的初始化{G[i].in = 0;G[i].out = 0;G[i].flag = 1;G[i].vertex = i;G[i].firstedge = NULL;}for(i = 0; i < NodeNum; i ++){for(j = 0; j < NodeNum; j ++){Relation[i][j] = 0;}}i = EdgeNum;while(i --) //表的填充{int node1;int node2;int w;cin>>node1>>node2>>w;Relation[node2][node1] = 1;ArcNode * temp = (ArcNode *)malloc(sizeof(ArcNode));temp->NodeId = node2;temp->weight = w;temp->next = NULL;count ++;EE[count] = node1;EL[count].node1 = node1;EL[count].node2 = node2;EL[count].Weight = w;temp->edgeId = count;G[node1].out ++;G[node2].in ++;ArcNode * pos = G[node1].firstedge;if(pos == NULL){G[node1].firstedge = temp;}else{while(1){if(pos->next == NULL) break;elsepos = pos->next;}pos->next = temp;}}MaxPathLen(NodeNum);return 0;
}

确定比赛名次

【问题描述】

此题为ACM竞赛真题，更强大的测试数据请自行前往以下链接进行代码提交验证。Problem - 1285 (hdu.edu.cn)

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

【输入形式】

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

【输出形式】

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

【样例输入】

4 3

1 2

2 3

4 3

【样例输出】

1 2 4 3

【样例说明】

符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

#include<iostream>
#define N 50
#include<stdlib.h>
#include<stack>
using namespace std;typedef struct node
{int nodeId;struct node * next;
}ArcNode;typedef struct
{int in;int flag;int advtex;ArcNode * firstedge;
}ALGraph;ALGraph G[N];int main()
{int NodeNum;int EdgeNum;cin>>NodeNum>>EdgeNum;int i = 0;for(i = 1; i <= NodeNum; i ++){G[i].advtex = i;G[i].in = 0;G[i].flag = 1;G[i].firstedge = NULL;}i = EdgeNum;while(i --){int node1;int node2;cin>>node1>>node2;G[node1].advtex = node1;G[node2].in ++;ArcNode * pos = G[node1].firstedge;ArcNode * temp = (ArcNode*)malloc(sizeof(ArcNode));temp->nodeId = node2;temp->next = NULL;if(pos == NULL)G[node1].firstedge = temp;else{while(1){if(pos->next == NULL)break;elsepos = pos->next;}pos->next = temp;}}stack<ALGraph*> S;for(i = 1; i <= NodeNum; i ++){if(G[i].in == 0){S.push(&G[i]);G[i].flag = 0;break;}}while(!S.empty()){ALGraph * p = S.top();S.pop();cout<<p->advtex<<" ";ArcNode * pos = p->firstedge;while(pos != NULL){G[pos->nodeId].in --;pos = pos->next;}for(i = 1; i <= NodeNum; i ++){if(G[i].in == 0 && G[i].flag == 1){S.push(&G[i]);G[i].flag = 0;break;}}}return 0;
}

割点

【问题描述】

求一个无向连通图的割点。割点的定义是：若删除此结点和与其相关联的边，无向图不再连通。

ACM竞赛中有一些涉及到连通分量、割点、割边、缩点等知识点相关的题目，做完此题大家可自行前往以下链接查看并思考类似的题目，自行提交代码验证。Problem - 4587 (hdu.edu.cn)

【输入形式】

第一行是顶点个数及边的条数，后续每一行是每条边的两端关联的两个顶点

【输出形式】

割点，若没有割点，则输出NO

【样例输入】

7 8

A B

A D

B C

C D

C G

D E

D F

E F

【样例输出】

C D

【样例输入】

5 7

A B

B C

B D

A D

C D

A E

E C

【样例输出】

NO

#include<iostream>
#define N 50
using namespace std;int R[N][N];
int Dfn[N];
int Low[N];
int root = 0;
bool res[N];
int timestamp = 0;
int NodeNum; //节点个数
int RelationNum; //边的条数void Tarjan(int p)
{Dfn[p] = Low[p] = ++ timestamp;int i = 0;int cnt = 0;for(i = 0; i < NodeNum; i ++){if(R[p][i] == 1){if(Dfn[i] == 0){Tarjan(i);Low[p] = min(Low[p], Low[i]);if(Dfn[p] <= Low[i]){cnt ++;if(p != root || cnt >= 2){res[p] = 1;}}}elseLow[p] = min(Low[p], Dfn[i]);}}
}int main()
{cin>>NodeNum>>RelationNum;int i, j;for(i = 0; i < NodeNum; i ++){for(j = 0; j < NodeNum; j ++){R[i][j] = 0;}}i = RelationNum;while(i --){char node1;char node2;cin>>node1>>node2;int n1 = int(node1) - 65;int n2 = int(node2) - 65;R[n1][n2] = R[n2][n1] = 1;}for(root = 0; root < NodeNum; root ++){if(Dfn[root] == 0) Tarjan(root);}bool IsGe = false;for(i = 0; i < NodeNum; i ++){if(res[i]){   cout<<char(i + 'A')<<" ";IsGe = true;}}if(IsGe == false) cout<<"NO";return 0;
}