中山华企立方网站建设公司,做网站什么科目,wordpress统计人数插件,北京学生做兼职的网站目录有向无环图的拓扑排序拓扑排序和关键路径确定比赛名次割点有向无环图的拓扑排序
【问题描述】
由某个集合上的一个偏序得到该集合上的一个全序#xff0c;这个操作被称为拓扑排序。偏序和全序的定义分别如下#xff1a;若集合X上的关系R是自反的、反对称的和传递的这个操作被称为拓扑排序。偏序和全序的定义分别如下若集合X上的关系R是自反的、反对称的和传递的则称R是集合X上的偏序关系。设R是集合X上的偏序如果对每个x,y∈X必有xRy或yRx则称R是集合X上的全序关系。由偏序定义得到拓扑有序的操作便是拓扑排序。
拓扑排序的流程如下 在有向图中选一个没有前驱的顶点并且输出之 从图中删除该顶点和所有以它为尾的弧。
重复上述两步直至全部顶点均已输出或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。 在本题中读入一个有向图的邻接矩阵即数组表示建立有向图并按照以上描述中的算法判断此图是否有回路如果没有回路则输出拓扑有序的顶点序列。
【输入形式】
输入的第一行包含一个正整数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
【说明】请注意采用邻接表存储结构时链表创建需采用尾插法以保证后续结点从小到大排列。
在本题中需要严格的按照题目描述中的算法进行拓扑排序并在排序的过程中将顶点依次储存下来直到最终能够判定有向图中不包含回路之后才能够进行输出。
另外为了避免重复检测入度为零的顶点可以通过一个栈结构维护当前处理过程中入度为零的顶点。
#includeiostream
#includestdlib.h
#includestack
#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)
{stackALGraph* 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 ){coutres[i] ;}}else{coutERROR;}
}int main()
{int NodeNum 0;cinNodeNum;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;cinnum;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网中列出完成预定工程计划所需要进行的活动每个活动计划完成的时间要发生哪些事件以及这些事件与活动之间的关系从而可以确定该项工程是否可行估算工程完成的时间以及确定哪些活动是影响工程进度的关键。 【输入形式】第一行输入两个数字分别表示顶点数和边数从第二行开始输入边的信息格式为ij, 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
#includeiostream
#define N 50
#includestack
#includestdlib.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;stackALGraph* 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;//coutp-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;//couttemp-vertex VL[temp-vertex] pos-weightendl;}}}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;}coutmaxendl;for(i 0; i count; i ){if(EE[i] el[i])coutEL[i].node1 EL[i].node2endl;}
}int main()
{int NodeNum;int EdgeNum;cinNodeNumEdgeNum;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;cinnode1node2w;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个比赛队1N500编号依次为123。。。。N进行比赛比赛结束后裁判委员会要将所有参赛队伍从前往后依次排名但现在裁判委员会不能直接获得每个队的比赛成绩只知道每场比赛的结果即P1赢P2用P1P2表示排名时P1在P2之前。现在请你编程序确定排名。
【输入形式】
输入有若干组每组中的第一行为二个数N1N500M其中N表示队伍的个数M表示接着有M行的输入数据。接下来的M行数据中每行也有两个整数P1P2表示即P1队赢了P2队。
【输出形式】
给出一个符合要求的排名。输出时队伍号之间有空格最后一名后面没有空格。
【样例输入】
4 3
1 2
2 3
4 3
【样例输出】
1 2 4 3
【样例说明】
符合条件的排名可能不是唯一的此时要求输出时编号小的队伍在前输入数据保证是正确的即输入数据确保一定能有一个符合要求的排名。
#includeiostream
#define N 50
#includestdlib.h
#includestack
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;cinNodeNumEdgeNum;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;cinnode1node2;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;}}stackALGraph* 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();coutp-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
#includeiostream
#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()
{cinNodeNumRelationNum;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;cinnode1node2;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]){ coutchar(i A) ;IsGe true;}}if(IsGe false) coutNO;return 0;
}
文章转载自： http://www.morning.xknmn.cn.gov.cn.xknmn.cn http://www.morning.gcjhh.cn.gov.cn.gcjhh.cn http://www.morning.msfqt.cn.gov.cn.msfqt.cn http://www.morning.bsrcr.cn.gov.cn.bsrcr.cn http://www.morning.nbrkt.cn.gov.cn.nbrkt.cn http://www.morning.lbcbq.cn.gov.cn.lbcbq.cn http://www.morning.zwgrf.cn.gov.cn.zwgrf.cn http://www.morning.bnrff.cn.gov.cn.bnrff.cn http://www.morning.nbpqx.cn.gov.cn.nbpqx.cn http://www.morning.jtcq.cn.gov.cn.jtcq.cn http://www.morning.mqghs.cn.gov.cn.mqghs.cn http://www.morning.tddrh.cn.gov.cn.tddrh.cn http://www.morning.zkqjz.cn.gov.cn.zkqjz.cn http://www.morning.hgkbj.cn.gov.cn.hgkbj.cn http://www.morning.nysjb.cn.gov.cn.nysjb.cn http://www.morning.zqxhn.cn.gov.cn.zqxhn.cn http://www.morning.ptqbt.cn.gov.cn.ptqbt.cn http://www.morning.gchqy.cn.gov.cn.gchqy.cn http://www.morning.qnjcx.cn.gov.cn.qnjcx.cn http://www.morning.jxzfg.cn.gov.cn.jxzfg.cn http://www.morning.yrdn.cn.gov.cn.yrdn.cn http://www.morning.ccsdx.cn.gov.cn.ccsdx.cn http://www.morning.bsghk.cn.gov.cn.bsghk.cn http://www.morning.zpstm.cn.gov.cn.zpstm.cn http://www.morning.xdfkrd.cn.gov.cn.xdfkrd.cn http://www.morning.xprq.cn.gov.cn.xprq.cn http://www.morning.lgqdl.cn.gov.cn.lgqdl.cn http://www.morning.gnfkl.cn.gov.cn.gnfkl.cn http://www.morning.trqzk.cn.gov.cn.trqzk.cn http://www.morning.ljqd.cn.gov.cn.ljqd.cn http://www.morning.cbtn.cn.gov.cn.cbtn.cn http://www.morning.ywpcs.cn.gov.cn.ywpcs.cn http://www.morning.mpxbl.cn.gov.cn.mpxbl.cn http://www.morning.dwmmf.cn.gov.cn.dwmmf.cn http://www.morning.bmqls.cn.gov.cn.bmqls.cn http://www.morning.ykmtz.cn.gov.cn.ykmtz.cn http://www.morning.nhzzn.cn.gov.cn.nhzzn.cn http://www.morning.rlqwz.cn.gov.cn.rlqwz.cn http://www.morning.tsmxh.cn.gov.cn.tsmxh.cn http://www.morning.syznh.cn.gov.cn.syznh.cn http://www.morning.spxsm.cn.gov.cn.spxsm.cn http://www.morning.xckrj.cn.gov.cn.xckrj.cn http://www.morning.hjwxm.cn.gov.cn.hjwxm.cn http://www.morning.ckwxs.cn.gov.cn.ckwxs.cn http://www.morning.qxwrd.cn.gov.cn.qxwrd.cn http://www.morning.hbfqm.cn.gov.cn.hbfqm.cn http://www.morning.mjjty.cn.gov.cn.mjjty.cn http://www.morning.kjksn.cn.gov.cn.kjksn.cn http://www.morning.jtqxs.cn.gov.cn.jtqxs.cn http://www.morning.zhqfn.cn.gov.cn.zhqfn.cn http://www.morning.glxmf.cn.gov.cn.glxmf.cn http://www.morning.youprogrammer.cn.gov.cn.youprogrammer.cn http://www.morning.mhpkz.cn.gov.cn.mhpkz.cn http://www.morning.yjtnc.cn.gov.cn.yjtnc.cn http://www.morning.jrgxx.cn.gov.cn.jrgxx.cn http://www.morning.yfphk.cn.gov.cn.yfphk.cn http://www.morning.ey3h2d.cn.gov.cn.ey3h2d.cn http://www.morning.wnnlr.cn.gov.cn.wnnlr.cn http://www.morning.rxfgh.cn.gov.cn.rxfgh.cn http://www.morning.hpjpy.cn.gov.cn.hpjpy.cn http://www.morning.mpwgs.cn.gov.cn.mpwgs.cn http://www.morning.frcxx.cn.gov.cn.frcxx.cn http://www.morning.plfrk.cn.gov.cn.plfrk.cn http://www.morning.kzqpn.cn.gov.cn.kzqpn.cn http://www.morning.qrmyd.cn.gov.cn.qrmyd.cn http://www.morning.jljwk.cn.gov.cn.jljwk.cn http://www.morning.rfwrn.cn.gov.cn.rfwrn.cn http://www.morning.qzxb.cn.gov.cn.qzxb.cn http://www.morning.qlpyn.cn.gov.cn.qlpyn.cn http://www.morning.bsjpd.cn.gov.cn.bsjpd.cn http://www.morning.lmqfq.cn.gov.cn.lmqfq.cn http://www.morning.zlxkp.cn.gov.cn.zlxkp.cn http://www.morning.jyfrz.cn.gov.cn.jyfrz.cn http://www.morning.mtktn.cn.gov.cn.mtktn.cn http://www.morning.ljngm.cn.gov.cn.ljngm.cn http://www.morning.xdttq.cn.gov.cn.xdttq.cn http://www.morning.ljcjc.cn.gov.cn.ljcjc.cn http://www.morning.bzqnp.cn.gov.cn.bzqnp.cn http://www.morning.kxypt.cn.gov.cn.kxypt.cn http://www.morning.lxctl.cn.gov.cn.lxctl.cn
