-Algorithm-baekjunPlatinumProblem/EditGraph.java at master · MoonDooo/-Algorithm-baekjunPlatinumProblem · GitHub

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
importjava.io.BufferedReader;
importjava.io.IOException;
importjava.io.InputStreamReader;
importjava.util.*;

/**
 * 백준 1432번 그래프 수정
 * author : MoonDooo
 */
publicclassMain {
publicstaticvoidmain(String[] args) {
newEditGraph();
 }
}
classEditGraph{
privatefinalBufbuf = newBuf();
privateintN;
privateNode[] nodes;
privateint[] result;
privatePriorityQueue<Integer> queue = newPriorityQueue<>((a,b)->Integer.compare(b,a));
publicEditGraph(){
initData();
for (inti = 0; i<N; i++){
if (nodes[i].getPre()==0){
queue.add(i);
 }
 }
if (queue.isEmpty()){
System.out.println(-1);
return;
 }
intcount = 0;
while(!queue.isEmpty()){
intnodeIdx = queue.poll();
result[nodes[nodeIdx].getNum()] = N-count;
count++;
for (inti = 0; i<nodes[nodeIdx].getLinkedNodeIdxList().size(); i++){
intlinkedNodeIdx = nodes[nodeIdx].getLinkedNodeIdxList().get(i);
nodes[linkedNodeIdx].reducePre();
if (nodes[linkedNodeIdx].getPre()==0){
queue.add(linkedNodeIdx);
 }
 }
 }

Arrays.stream(result).forEach(r->{
if (r==0){
System.out.println(-1);
System.exit(0);
 }
 });
Arrays.stream(result).forEach(r-> System.out.print(r+" "));
 }
publicvoidinitData(){
N = buf.nextInt();
nodes = newNode[N];
for (inti = 0; i<N; i++){
nodes[i] = newNode(i);
 }
result = newint[N];
for (inti =0; i<N; i++){
Stringinput = buf.next();
for (intj = 0; j<N; j++){
if (input.charAt(j)=='1'){
nodes[j].addLinkedNodeIdx(i);
nodes[i].increasePre();
 }
 }
 }
 }
}
classNode{
privateintnum;
privateList<Integer> linkedNodeIdxList = newArrayList<>();

publicintgetPre() {
returnpre;
 }
publicvoidincreasePre(){
this.pre++;
 }
publicvoidreducePre(){
this.pre--;
 }

privateintpre;

publicNode(intnum) {
this.num = num;
this.pre = 0;
 }

publicintgetNum() {
returnnum;
 }

publicList<Integer> getLinkedNodeIdxList() {
returnlinkedNodeIdxList;
 }
publicvoidaddLinkedNodeIdx(intidx){
linkedNodeIdxList.add(idx);
 }
}
classBuf{
BufferedReaderbr;
StringTokenizerst;
Buf(){
br= newBufferedReader(newInputStreamReader(System.in));
 }
Stringnext(){
while(st==null||!st.hasMoreElements()){
try{
st= newStringTokenizer(br.readLine());
 }catch(IOExceptione){
e.printStackTrace();
 }
 }
returnst.nextToken();
 }
intnextInt(){
returnInteger.parseInt(next());
 }
longnewLong(){
returnLong.parseLong(next());
 }
}