Pagini recente » Cod sursa (job #1965541) | Cod sursa (job #2427946) | Cod sursa (job #116948) | Cod sursa (job #858019) | Cod sursa (job #1776200)
import java.io.*;
import java.util.Scanner;
class Node {
private int info;
private Node next;
public Node() {
this.next = null;
this.info = -1;
}
public Node(int info) {
this.info = info;
this.next = null;
}
public void setInfo(int info) {
this.info = info;
}
public void setNext(Node next) {
this.next = next;
}
public int getInfo() {
return info;
}
public Node getNext() {
return next;
}
}
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() {
this.marked = new boolean[this.graph.length];
int cnt = 0;
for(int i = 1; i < this.graph.length; i++) {
if(!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 e = new FileReader(this.inputFile);
Scanner input = new Scanner(e);
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.setNext(this.graph[i]);
this.graph[i] = node1;
Node node2 = new Node(j);
node2.setNext(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.getNext()) {
if (!this.marked[node.getInfo()]) {
this.dfs(node.getInfo());
}
}
}
}
public class Main {
public static void main(String[] args) {
Problem problem = new Problem("dfs.in", "dfs.out");
problem.solve();
problem.writeSolutionToFile();
}
}