算法分析
很裸的拓扑排序,直接套拓扑排序模版
思考:如何输出字典序最小的拓扑排序?
- 将队列换成优先队列,优先队列取出的元素是当前字典序最小的编号,在出队的时候记录出队的编号即为当前字典序最小的拓扑序,此方法的时间复杂度是$O(logn * (n + m))$
注意:由于点的个数最多是是N
,即使所有点都连上了有向边,最多的边数是(n * (n - 1))/2
条,因此开到M
需要开到N * N / 2
时间复杂度 $O(n + m)$
参考文献
算法提高课
Java 代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N = 110;
static int M = N * N / 2;
static int n;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int idx = 0;
static int[] qv = new int[N];
static int qidx = 0;
static int[] d = new int[N]; //记录每个点的入度个数
static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
static void topsort()
{
Queue<Integer> q = new LinkedList<Integer>();
for(int i = 1;i <= n;i ++)
{
if(d[i] == 0)
{
q.add(i);
qv[qidx ++] = i;
}
}
while(!q.isEmpty())
{
int t = q.poll();
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
d[j] --;
if(d[j] == 0)
{
q.add(j);
qv[qidx ++] = j;
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
Arrays.fill(h, -1);
for(int i = 1;i <= n;i ++)
{
while(true)
{
int b = scan.nextInt();
if(b == 0) break;
add(i,b);
d[b] ++;
}
}
topsort();
for(int i = 0;i < qidx;i ++) System.out.print(qv[i] + " ");
}
}
输出字典序最小
Java 代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N = 110;
static int M = N * N / 2;
static int n;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int idx = 0;
static int[] qv = new int[N];
static int qidx = 0;
static int[] d = new int[N]; //记录每个点的入度个数
static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
static void topsort()
{
PriorityQueue<Integer> q = new PriorityQueue<Integer>();
for(int i = 1;i <= n;i ++)
{
if(d[i] == 0)
{
q.add(i);
}
}
while(!q.isEmpty())
{
int t = q.poll();
qv[qidx ++] = t;
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
d[j] --;
if(d[j] == 0)
{
q.add(j);
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
Arrays.fill(h, -1);
for(int i = 1;i <= n;i ++)
{
while(true)
{
int b = scan.nextInt();
if(b == 0) break;
add(i,b);
d[b] ++;
}
}
topsort();
for(int i = 0;i < qidx;i ++) System.out.print(qv[i] + " ");
}
}