relations

注意测试数据保证一定可以完成所有课程也就是先修课的关系构成一个有向无环图。

输入n

解释上图展示了输入数据所表示的先修关系图以及完成每门课程需要花费的时间。

同时开始课程

[[1,5],[2,5],[3,5],[3,4],[4,5]],

time

解释上图展示了输入数据所表示的先修关系图以及完成每门课程需要花费的时间。

同时开始课程

思路使用二维数组g利用邻接表的方式建图其中g[i]表示i的出边集合使用一维数组deg表示节点的先驱个数使用队列q表示入度为0的队列并将deg[i]为0的节点加入队列使用一维数组f表示完成该课程的最少月份数当deg为0时ftime反之fmax(f…)time。

注意*max_element(f.begin(),f.end())求最大值。

class

xr[0]-1,yr[1]-1;g[x].push_back(y);deg[y];}//拓扑队列queueint

q;for(int

i0;in;i)if(deg[i]0)q.push(i);vectorint

xq.front();q.pop();//x出队意味着x的所有先修课都上完了f[x]time[x];for(int

y:g[x])

y的f值是其所有先修课的f值的最大值if(--deg[y]0)q.push(y);}}return

*max_element(f.begin(),f.end());}

};总结拓扑排序