Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
InputChecker of problemE in WUPC2nd.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
public class InputCheckerE {
public static void main(String[] args) throws Exception {
String[] substasks = new String[]{"nonloop", "loop"};
for (String substask : substasks) {
File inputDir = new File("/path/to/the/input/data/" + substask);
for (File file : inputDir.listFiles()) {
BufferedReader reader = new BufferedReader(new FileReader(file));
if (!check(reader, "loop".equals(substask) ? 1 : 0)) {
System.err.println("err:" + file.getName());
} else {
System.err.println("ok");
}
reader.close();
}
}
}
private static boolean check(BufferedReader reader, int allowedLoop) {
try {
String[] line = reader.readLine().split(" ");
if (line.length != 3) {
return false;
}
int N = Integer.valueOf(line[0]);
int M = Integer.valueOf(line[1]);
int K = Integer.valueOf(line[2]);
if (1 <= N && N <= 100) {
} else {
System.err.println("invalid N");
return false;
}
if (0 <= M && M <= N) {
} else {
System.err.println("invalid M");
return false;
}
if (1 <= K && K <= N) {
} else {
System.err.println("invalid K");
return false;
}
boolean[][] graph = new boolean[N+1][N+1];
int[] degs = new int[N+1];
for (int i = 0 ; i < M ; i++) {
String[] road = reader.readLine().split(" ");
if (road.length != 3) {
return false;
}
int f = Integer.valueOf(road[0]);
int t = Integer.valueOf(road[1]);
int c = Integer.valueOf(road[2]);
if (1 <= f && f <= N) {
} else {
System.err.println("invalid f");
return false;
}
if (1 <= t && t <= N) {
} else {
System.err.println("invalid t");
return false;
}
if (1 <= c && c <= 1000000) {
} else {
System.err.println("invalid cost");
return false;
}
if (f == t) {
System.err.println("self loop");
return false;
}
if (graph[f][t]) {
System.err.println("double");
return false;
}
graph[f][t] = true;
graph[t][f] = true;
degs[f]++;
degs[t]++;
}
while (true) {
boolean updated = false;
for (int i = 1 ; i <= N ; i++) {
if (degs[i] == 1) {
updated = true;
degs[i]--;
for (int j = 1 ; j <= N ; j++) {
if (i == j || !graph[i][j]) {
continue;
}
degs[j]--;
}
}
}
if (!updated) {
break;
}
}
if (allowedLoop == 0) {
for (int i = 1 ; i <= N ; i++) {
if (degs[i] >= 1) {
return false;
}
}
} else {
int gcnt = 0;
visited = new boolean[N+1];
for (int i = 1 ; i <= N ; i++) {
if (degs[i] >= 2) {
if (degs[i] != 2) {
System.err.println("invalid degrees:" + degs[i]);
return false;
}
if (!visited[i]) {
gcnt++;
dfs(i, N, graph);
}
}
}
if (gcnt != 1) {
System.err.println("invalid number of loops:" + gcnt);
return false;
}
}
return true;
} catch (Exception e) {
return false;
}
}
static boolean[] visited;
public static void dfs(int i, int N, boolean[][] g) {
if (visited[i]) {
return;
}
visited[i] = true;
for (int j = 1 ; j <= N ; j++) {
if (g[i][j]) {
dfs(j, N, g);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment