力扣周赛

力扣周赛"/>

力扣周赛

先更新前两道题目，下午更新后两道

两道模板题(拓扑排序)

拓扑排序

拓扑排序（Topological Sorting）：一种对有向无环图（DAG）的所有顶点进行线性排序的方法，使得图中任意一点 $u$ 和 $v$，如果存在有向边 $<u, v>$，则 $u$ 必须在 $v$ 之前出现。对有向图进行拓扑排序产生的线性序列称为满足拓扑次序的序列，简称拓扑排序。

拓扑排序解决的主要问题？

拓扑排序可以用来解决一些依赖关系的问题，比如项目的执行顺序，课程的选修顺序等。

 刚开始我的思路是，先想的是并查集，但是看了第二题(提示有向无环图)就先想拓扑排序了，第一道题的代码复制一下到第二题基本就可以解决第二道题(其实只要建出来拓扑序列，判断入度为0的有几个就行，超过2个就没有，不需要排序，我排序是因为自己默写一下拓扑排序)

 差分约束应该也是可以实现的

 但是我这里采用更为简单的做法，拓扑排序

 拓扑排序可以解决一系列具有依赖关系的问题，例如家谱树，课程表等等问题

 前三题为板子题

class Solution {
public:int din[310];int dou[310];int h[11010],ne[11010],e[11010],idx;queue<int> q;int sort_d[110];int sid = 0;void top_sort(int n){for(int i = 0;i < n;i++){if(!din[i]) q.push(i);}while(!q.empty()){auto t = q.front();q.pop();sort_d[sid++] = t;for(int i = h[t];i != -1;i = ne[i]){int b = e[i];//i是对应点的虚拟编号(相当于索引),正式编号是e[i]din[b]--;if(!din[b]){q.push(b);}}}}void add(int a,int b){e[idx] = b,ne[idx] = h[a],h[a] = idx++;}int findChampion(vector<vector<int>>& grid) {int n = grid.size();memset(h,-1,sizeof(h));memset(sort_d,-1,sizeof(sort_d));for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){if(i != j){int a_team = i;int b_team = j;if(grid[i][j]){//a队强din[b_team]++;dou[a_team]++;add(a_team,b_team);}else{//b队强din[a_team]++;dou[b_team]++;add(b_team,a_team);}}}}top_sort(n);if(sort_d[0] == -1) return -1;return sort_d[0];}
};

 第二题也是板子题，跟第一题没什么区别，复制第一题的代码改一下就行了

class Solution {
public:int din[310];int dou[310];int h[111010],ne[111010],e[111010],idx;queue<int> q;int sort_d[110];int sid = 0;bool flag = false;void top_sort(int n){for(int i = 0;i < n;i++){if(!din[i]) q.push(i);}if(q.size() > 1){flag = true;return ;}while(!q.empty()){auto t = q.front();q.pop();sort_d[sid++] = t;for(int i = h[t];i != -1;i = ne[i]){int b = e[i];//i是对应点的虚拟编号(相当于索引),正式编号是e[i]din[b]--;if(!din[b]){q.push(b);}}}}void add(int a,int b){e[idx] = b,ne[idx] = h[a],h[a] = idx++;}int findChampion(int n,vector<vector<int>>& edge) {memset(h,-1,sizeof(h));memset(sort_d,-1,sizeof(sort_d));int size_edge = edge.size();for(int i = 0;i < edge.size();i++){int a = edge[i][0];int b = edge[i][1];//a队强add(a,b);din[b]++;dou[a]++;}top_sort(n);if(flag) return -1;return sort_d[0];}
};