如题= =自用模板

dfs序+普通求字典序最小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//dfs序 只能求任意一组解 结果逆序保存在res中
class TopSort{
int[]head; //点下标从0~n-1
Edge[]edge;
int[]vis;
int cnt;
int maxn=12150;
int maxm=20050;
int st;
int[]res;//逆序结果
TopSort(){
head=new int[maxn];
edge=new Edge[maxm];
for(int i=0;i<maxm;i++)edge[i]=new Edge();
vis=new int[maxn];
res=new int[maxn];
}
void init(){
Arrays.fill(head, -1);
cnt=0;
st=0;
}
boolean sort(int n){
Arrays.fill(vis, 0);
for(int i=n-1;i>=0;i--){
if(vis[i]==0){
if(!dfs(i))return false; //有环
}
}
return true;
}
boolean dfs(int u){
vis[u]=-1;
for(int i=head[u];i!=-1;i=edge[i].next){
int to=edge[i].to;
if(vis[to]==-1)return false;
if(vis[to]==0){
dfs(to);
}
}
vis[u]=1;
res[st++]=u;
return true;
}
void add_diredge(int u,int v,int w){
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
}
class Edge{
int to,next,w;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//普通求字典序最小
import java.io.*;
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
TopSort ts=new TopSort();
while(sc.hasNext()){
int n=sc.nextInt();
int m=sc.nextInt();
ts.init();
for(int o=1;o<=m;o++){
int a=sc.nextInt();
int b=sc.nextInt();
ts.add_diredge(a-1, b-1, 1);
}
ts.sort(n);
for(int i=0;i<ts.st;i++){
if(i==ts.st-1)pw.println(ts.res[i]+1);
else pw.print((ts.res[i]+1)+" ");
}
pw.flush();
}
}

}
class TopSort{
int[]head;
Edge[]edge;
int cnt;
int maxn=10050;
int maxm=20050;
int st;
int[]du;
int[]res;
PriorityQueue<Integer>queue;
TopSort(){
head=new int[maxn];
edge=new Edge[maxm];
for(int i=0;i<maxm;i++)edge[i]=new Edge();
du=new int[maxn];
res=new int[maxn];
queue=new PriorityQueue();
}
void init(){
queue.clear();
Arrays.fill(head,-1);
st=0;
cnt=0;
}
void sort(int n){
for(int i=0;i<n;i++){
if(du[i]==0)queue.add(i);
}
while(!queue.isEmpty()){
int u=queue.poll();
res[st++]=u;
for(int i=head[u];i!=-1;i=edge[i].next){
int to=edge[i].to;
du[to]--;
if(du[to]==0)queue.add(to);
}
}
}
void add_diredge(int u,int v,int w){
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
du[v]++;
}
}
class Edge{
int to,next,w;
}