牛客_AB13【模板】拓扑排序

【模板】拓扑排序_牛客题霸_牛客网 (nowcoder.com)

描述：

        给定一个包含nn个点mm条边的有向无环图，求出该图的拓扑序。若图的拓扑序不唯一，输出任意合法的拓扑序即可。若该图不能拓扑排序，输出−1。

---

题目解析

1. 建图。
2. 入队为 0 的点入队。
3. 最后来一次层序遍历即可。

C++代码

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 2 * 1e5 + 1;
int main()
{int n = 0, m = 0;cin >> n >> m;int x = 0, y = 0;unordered_map<int, vector<int>> Edge;vector<int> in(N);while (cin >> x >> y) // x 指向 y{Edge[x].push_back(y);in[y]++;}// for(auto& [a, b] : Edge)// {// cout << a << " -> ";// for(auto& e : b)// {// cout << e << " ";// }// cout << endl;// }// for(auto& e : in)// {// if(e != 0)// cout << e << " ";// }// cout << endl;priority_queue<int> q;for (int i = 1; i <= n; ++i){if (in[i] == 0){q.push(i);// cout << "begin" << i;}}vector<int> res;while (q.size()){int tmp = q.top();q.pop();res.push_back(tmp);for (auto& e : Edge[tmp]) // tmp指向的边的入度减一{in[e]--;if (in[e] == 0) // 减为0了就进队列q.push(e);}// // Edge.erase(tmp); // 加这步?// for(auto& [a, b] : Edge)// {// cout << a << " -> ";// for(auto& e : b)// {// cout << e << " ";// }// cout << endl;// }// for(int i = 1; i <= n; ++i)// {// cout << in[i] << " ";// }// cout << endl;}if(res.size() != n){cout << -1;}else{for (int i = 0; i < n - 1; ++i){cout << res[i] << " ";}cout << res[n - 1]; // 666666666666666}return 0;
}

Java代码

import java.util.*;
import java.io.*;
public class Main
{public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static int n, m;public static Map<Integer, List<Integer>> edges = new HashMap<>(); // 存储图public static int[] cnt; //统计⼊度信息public static void main(String[] args) throws IOException{n = in.nextInt(); m = in.nextInt();cnt = new int[n + 1];// 1. 建图for(int i = 0; i < m; i++){int a = in.nextInt(), b = in.nextInt();// a -> bcnt[b]++;if(!edges.containsKey(a)){edges.put(a, new ArrayList<>());}edges.get(a).add(b);}// 2. 拓扑排序Queue<Integer> q = new LinkedList<>();for(int i = 1; i <= n; i++){if(cnt[i] == 0){q.add(i);}}int[] ret = new int[n]; // 统计拓扑排序的结果int pos = 0;while(!q.isEmpty()){int t = q.poll();ret[pos++] = t;for(int a : edges.getOrDefault(t, new ArrayList<>())){cnt[a]--;if(cnt[a] == 0){q.add(a);}}}if(pos == n){// 输出结果：输出最后⼀个数的时候，不能有空格for(int i = 0; i < n - 1; i++){out.print(ret[i] + " ");}out.println(ret[n - 1]);}else{out.println(-1);}out.close();}
}
class Read // ⾃定义快速读⼊
{StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException {while(!st.hasMoreTokens()){st = new StringTokenizer(bf.readLine());}return st.nextToken();}String nextLine() throws IOException {return bf.readLine();}int nextInt() throws IOException {return Integer.parseInt(next());}long nextLong() throws IOException {return Long.parseLong(next());}double nextDouble() throws IOException {return Double.parseDouble(next());}
}