现在给出一张含有 n 个点的有向无环图,我们称这张图是“有序图”当且仅当这个图满足以下条件:
1. 存在一个 1-n 数字的全排列 p ,并令 i 号结点的权值为 p[i] 。
2. 如果图中存在 u 号结点到 v 号结点的一条边,则 u 号结点的权值要小于 v 号结点的权值。 显然可能有多个序列满足条件,请你找出字典序最小的全排列 p ,使得这个图成为有序图。
数据范围:
第一行包含两个正整数n,m,分别表示图上结点是数量和有向边的数量。 接下来m行每行有两个正整数u,v,表示存在一条从u结点到v结点的有向边。
输出一个字典序最小的,1-n的全排列,使得这张图是有序图,元素中间使用空格隔开。
3 3 1 2 1 3 3 2
1 3 2
#include <bits/stdc++.h> using namespace std; const int M = 100003; vector<int> E[M]; int indegree[M]; int main(){ int n, m, u, v; cin>>n>>m; int r[n+1]; for(int i=0;i<m;i++){ cin>>u>>v; E[v].push_back(u); indegree[u]++; } priority_queue<int> q; for(int i=1;i<=n;i++) if(!indegree[i]) q.push(i); int k = n; while(!q.empty()){ int p = q.top(); q.pop(); r[p] = k--; for(int i=0;i<E[p].size();i++){ v = E[p][i]; indegree[v]--; if(indegree[v]==0) q.push(v); } } for(int i=1;i<=n;i++){ if(i==n) cout<<r[i]<<endl; else cout<<r[i]<<" "; } return 0; }
import java.util.Scanner; import java.util.ArrayList; import java.util.PriorityQueue; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int n = in.nextInt(); int m = in.nextInt(); ArrayList<Integer> from[] = new ArrayList[n + 1]; // 保存1-n每个节点的前置节点 int hash[] = new int[n + 1]; // 保存1-n每个节点的出度 // 初始化from和hash for (int i = 0; i < m; i++) { int pre = in.nextInt(); int next = in.nextInt(); if (from[next] == null) from[next] = new ArrayList<>(); from[next].add(pre); hash[pre]++; } // 最大优先队列 PriorityQueue<Integer> q = new PriorityQueue<>(((o1, o2) -> o2 - o1)); int w = n; // 最大权重 int ant[] = new int[n + 1]; // 1-n每个节点对应的权值数组 // 下面是拓扑排序过程,顺便为每个节点赋权值 for (int i = 1; i < n + 1; i++) { // 将出度为0的节点添加到队列,(出度为0即最后一个节点) if (hash[i] == 0) { q.add(i); } } while (!q.isEmpty()) { int t = q.poll(); ant[t] = w; // 依次为每个节点赋权值 w--; if (from[t] != null) { for (int i : from[t]) { hash[i]--; if (hash[i] == 0) q.add(i); } } } for (int i = 1; i < n + 1; i++) { System.out.print(ant[i] + " "); } } } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Comparator; import java.util.PriorityQueue; /** * @Author: coderjjp * @Date: 2020-05-11 22:27 * @Description: * @version: 1.0 */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line1 = br.readLine().split(" "); int n = Integer.parseInt(line1[0]); int m = Integer.parseInt(line1[1]); int hash[] = new int[n+1];//记录1-n的出度 ArrayList<Integer> from[] = new ArrayList[n+1];//记录每个点被谁指向 for (int i = 0; i < m; i++){ String line[] = br.readLine().split(" "); int f = Integer.parseInt(line[0]); int t = Integer.parseInt(line[1]); if (from[t] == null) from[t] = new ArrayList<>(); from[t].add(f); hash[f]++; } //维护一个最大优先队列 PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);//将出度为0的进队 for (int i = 1; i <= n; i++) if (hash[i] == 0) queue.offer(i); int ans[] = new int[n+1];//记录1-n个节点的权重 int w = n; while (!queue.isEmpty()){ int cur = queue.poll(); ans[cur] = w; w--; if (from[cur] != null) for (int i: from[cur]){ hash[i]--; if (hash[i] == 0) queue.offer(i); } } StringBuilder res = new StringBuilder().append(ans[1]); for (int i = 2; i <= n; i++) res.append(" ").append(ans[i]); System.out.println(res); } }
from collections import defaultdict import queue graph,opp_graph,out = defaultdict(list),defaultdict(list),defaultdict(int) n,m = map(int,input().split()) q = queue.PriorityQueue() for _ in range(m): x,y = map(int,(input().split())) graph[x].append(y) opp_graph[y].append(x) for d in range(1,n+1): out[d] = len(graph[d]) if out[d]==0: q.put(-d) ans ,count= [0 for i in range(n)],n while not q.empty(): node = -q.get() ans[node-1] = count count-=1 for d in opp_graph[node]: out[d] -= 1 if out[d]==0: q.put(-d) print(' '.join(list(map(str,ans))))
#include <bits/stdc++.h> //freopen("temp.in","r",stdin);(1522)#include "utils.cpp" using namespace std; #define UF(i,start,end) for(auto i=start;i<end;i++) (1523)#define DF(i,start,end) for(auto i=start;i>=end;i--) int ri(){int a;scanf("%d",&a);return a;}//读取整数并返回 string rs(){string s;cin>>s;return s;} typedef long long ll; typedef vector<int> veci; typedef vector<bool> vecb; typedef vector<string> vecs; typedef vector<vector<int>> vveci; veci split(string s,char c){ veci V; int i=0,j=1,n=s.length(); while(i<n){ while(j<n and s[j]!=c) j++; if(j==n-1) j++; V.push_back(atoi(s.substr(i,j-i).c_str())); i=j+1; j++; } return V; } template<typename T> ostream& operator<<(ostream& os,const vector<T>& v){ for(auto t:v) os<<t<<" "; os<<endl; return os; } template <typename T> ostream &print(ostream &os,const T &t){ return os<<t<<endl; } template <typename T,typename... Args> ostream &print(ostream &os,const T &t,const Args&... rest){ os << t <<" "; return print(os,rest...); } template <typename T,typename... Args> void PR(const T &t,const Args&... rest){ print(cout,t,rest...); } template <typename T> void reverse(T &t){ reverse(t.begin(),t.end()); } struct BigInteger{ veci data; int size; BigInteger():size(0){} BigInteger(int val){ size = 0; while(val){ size++; data.push_back(val%10); val/=10; } } void multiply(BigInteger b){ veci T(size,0); int temp = size; UF(i,0,b.size){ UF(j,0,temp){ if(j+i>=size){ size++; T.push_back(data[j]*b.data[i]); }else T[j+i]+=data[j]*b.data[i]; } } temp = size; UF(i,0,temp){ if(T[i]>9){ if(i==temp-1){ size++; T.push_back(T[i]/10); }else T[i+1]+=T[i]/10; T[i]%=10; } } data.assign(T.begin(),T.end()); } void print(){ DF(i,size-1,0){ cout<<data[i]; } cout<<endl; } }; int random(int k){ return rand()%k+1; } vector<int> create_data(){ PR(random(10),random(20)); } void test(){ unsigned seed = time(0); srand(seed); freopen("temp.out", "w", stdout); int N=5;//生成测试数据组数 for(int i=0;i<N;i++) create_data(); } //拓扑 int MAX_N=100000; vveci G(MAX_N); int main(){ //freopen("temp.in","r",stdin); //test(); int n,m; cin>>n>>m;//写成模板输入 int u,v; /* 拓扑排序+优先级队列 参考了别人的代码才理解 题目要求最小字典序,则要从后往前排没有出度的节点,为什么不从前往后呢,因为前 面的节点会受指向它的节点的排序影响 10 10 9 7 5 2 10 2 5 8 1 2 10 7 3 2 4 2 8 7 1 8 对应输出应该为: 1 6 2 3 4 7 10 8 9 5 */ veci C(n+1,0);//出度 priority_queue<int,vector<int>,less<int> > Q;//大的优先 从大到小出队列 UF(i,0,m){ cin>>u>>v; G[v].push_back(u);//G[v] 指向v的边 而不是v指向别人 C[u]+=1;//从u点出的边个数 } veci ans(n+1); int k=0; UF(i,1,n+1){ if(C[i]==0) Q.push(i);//将出度为0的点入队列 } int cnt=n; while(cnt>0){ auto a=Q.top(); Q.pop(); ans[a]=cnt--;//让编号较小节点的保留更大的编号,先让后面编号大的又没有输出的点先排序 for(auto b:G[a]){//将指向自身的边的出度-1 C[b]--; if(C[b]==0){ Q.push(b);//没有出度时入队列 } } } UF(i,1,n) cout<<ans[i]<<" "; cout<<ans[n]<<endl; return 0; }