图论 - wenzhoullq/leetcode GitHub Wiki
int[] rudu=new int[n];
HashMap<Integer,List<Integer>> m=new HashMap<>();//临界表
for(int[] edge:edgss) rudu[edge[1]]++;
for(int i=0;i<n;i++) m.put(i,new ArrayList<>());
Queue<Integer> q=new LinkedList<>();
for(int i=0;i<rudu.length;i++){
if(rudu[i]==0) q.add(i);
}
while(!q.isEmpty()){
int size=q.size();
int cur=q.poll();
List<Integer> list=m.get(cur);
for(int temp:list){
int temp=list.get(j)
rudu[temp]--;
if(rudu[temp]==0) q.add(temp);
}
}
851. 喧闹和富有 找爸爸中比它大的,从爸爸开始找起,并且用一个arr数组保存最大值
6163. 给定条件下构造矩阵 y和x是独立的,独立记录即可,二维课程表
只有一个出度的就是内向基环树
- 找环
思路是去除所有非拓扑排序的,剩下的就是拓扑排序
2127. 参加会议的最多员工数 再加一个长度为2的回环它的两侧,即时间戳
- 找路径
6134. 找到离给定两个节点最近的节点 把所有的能访问的点都访问了
边的权值不能为负数
class route{//星链存储,剪枝
int index ;
int val ;
route(int index , int val){
this.index = index;
this.val = val;
}
}
int[][] distance = new int[n][n];
int INF = Integer.MAX_VALUE/4;
LinkedList<route>[] list = new LinkedList[n];
for(int i = 0 ; i < n; i++){
Arrays.fill(distance[i],INF);
distance[i][i] = 0;
list[i] = new LinkedList<>();
}
for(int[] edge:edges){
distance[edge[0]][edge[1]] = edge[2];
distance[edge[1]][edge[0]] = edge[2];
list[edge[0]].add(new route(edge[1],edge[2]));
list[edge[1]].add(new route(edge[0],edge[2]));
}
boolean[] visit = new boolean[n];
Queue<int[]> q = new PriorityQueue<>((a,b)->a[1] - b[1]);
q.add(new int[]{k,0});//第一个是点,第二个是边的权重
while(!q.isEmpty()){
int[] temp = q.poll();
int start = temp[0];
if(visit[start]) continue;//剪枝
visit[start] = true;
for (route r : list[start]) {
if (visit[r.index] || distance[start][r.index] == INF) continue;
if (rank + r.val <= distance[k][r.index]) {
distance[k][r.index] = rank + r.val;
q.add(new int[]{r.index, distance[k][r.index]});
}
}
}
公交线路 裸题