Pagini recente » Cod sursa (job #840820) | Cod sursa (job #1084600) | Cod sursa (job #1031112) | Cod sursa (job #2260771) | Cod sursa (job #1776204)
import java.io.*;
import java.util.Scanner;
class Node {
public int info;
public Node next;
public Node() {
this.next = null;
this.info = -1;
}
public Node(int info) {
this.info = info;
this.next = null;
}
}
class Problem {
private String inputFile ;
private String outputFile;
private Node[] graph;
private int solution;
private boolean solved;
private boolean wroteSolution;
private String fileEncoding;
private boolean[] marked;
public Problem(String inputFile, String outputFile) {
this.inputFile = inputFile;
this.outputFile = outputFile;
this.solved = false;
this.fileEncoding = "UTF-8";
this.graph = null;
this.marked = null;
this.readGraph();
}
public void solve() {
int len = this.graph.length;
this.marked = new boolean[len];
int cnt = 0;
for(int i = 1; i < len; ++i) {
if(!this.marked[i]) {
this.dfs(i);
++cnt;
}
}
this.solution = cnt;
this.solved = true;
}
public int getSolution() {
if (!this.solved) {
throw new UnsupportedOperationException();
}
return solution;
}
public void writeSolutionToFile() {
if (this.wroteSolution) {
throw new UnsupportedOperationException();
}
try {
PrintWriter writer = new PrintWriter(this.outputFile, this.fileEncoding);
writer.println(this.getSolution());
writer.close();
} catch (FileNotFoundException | UnsupportedEncodingException e) {
e.printStackTrace();
}
this.wroteSolution = true;
}
private void readGraph() {
if(this.graph == null) {
try {
FileReader reader = new FileReader(this.inputFile);
Scanner input = new Scanner(reader);
int n = input.nextInt();
int m = input.nextInt();
for(this.graph = new Node[n + 1]; m > 0; --m) {
int i = input.nextInt();
int j = input.nextInt();
Node node1 = new Node(j);
node1.next = this.graph[i];
this.graph[i] = node1;
Node node2 = new Node(i);
node2.next = this.graph[j];
this.graph[j] = node2;
}
} catch (IOException var9) {
var9.printStackTrace();
}
}
}
private void dfs(int startNode) {
this.marked[startNode] = true;
for (Node node = this.graph[startNode]; node != null; node = node.next) {
if (!this.marked[node.info]) {
this.dfs(node.info);
}
}
}
}
public class Main {
public static void main(String[] args) {
Problem problem = new Problem("dfs.in", "dfs.out");
problem.solve();
problem.writeSolutionToFile();
}
}