-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathA1003.java
More file actions
144 lines (127 loc) · 3.39 KB
/
A1003.java
File metadata and controls
144 lines (127 loc) · 3.39 KB
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*******************************************************************************
* Copyright (c) 2017 ejpark.
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the GNU General Public License v3.0
* which accompanies this distribution, and is available at
* http://www.gnu.org/licenses/gpl-3.0.html
*
* Contributors:
* eungjun11@gmail.com - initial API and implementation
******************************************************************************/
package algorithm.li;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* @author ejpark
*
*/
public class A1003 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int n = Integer.parseInt(input);
int[][] graph = new int[n][n];
for (int i = 0; i < n; i++) {
String line = br.readLine();
for (int j = 0; j < n; j++) {
graph[i][j] = line.charAt(j) - 48;
}
}
int m = Integer.parseInt(br.readLine());
Map<Integer, List<Integer>> map = new HashMap<>();
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
int position = graph[i][j];
if(position==1) {
List<Integer> nodeList = map.get(i);
if(nodeList == null) {
nodeList = new ArrayList<Integer>();
map.put(i, nodeList);
}
nodeList.add(j);
}
}
}
List<Node> list = new ArrayList<Node>();
for(int i=0; i<n; i++) {
Node node = new Node();
node.setDepth(0);
node.setType(i);
List<Integer> edgelist = map.get(i);
addChild(node, edgelist, 0, map, m);
list.add(node);
}
boolean isCycle = false;
for(Node root : list) {
System.out.println("RootNode:"+root);
int cycleType = getType(root, m, root.getType());
if(cycleType == 1) {
isCycle = true;
break;
}
}
if(isCycle) {
System.out.println(1);
}else {
System.out.println(0);
}
// O(n+(n*(n-1))
}
private static int getType(Node node, int depth, int root) {
System.out.println("node:"+node);
System.out.println("depth:"+ depth+", root:" + root);
if(node.getDepth() == depth && node.getType() == root) {
return 1;
}
List<Node> nodeList = node.getChildren();
for(Node child :nodeList) {
return getType(child, depth, root);
}
return 0;
}
private static void addChild(Node node, List<Integer> edgelist, int depth, Map<Integer, List<Integer>> map, int max) {
depth++;
for(int edge : edgelist) {
Node child = new Node();
child.setDepth(depth);
child.setType(edge);
node.addNode(child);
if(depth < max) {
addChild(child, map.get(edge), depth, map, max);
}
}
}
static class Node {
int type;
int depth;
List<Node> nodeList = new ArrayList<Node>();
public void setType(int type) {
this.type = type;
}
public void setDepth(int depth) {
this.depth = depth;
}
public void addNode(Node node) {
this.nodeList.add(node);
}
public void addAll(List<Node> nodelist) {
this.nodeList.addAll(nodelist);
}
public int getType() {
return this.type;
}
public int getDepth() {
return this.depth;
}
public List<Node> getChildren(){
return nodeList;
}
public String toString() {
return String.format("[type:%s, depth:%s, child:%s]", type, depth, nodeList);
}
}
}