Cod sursa(job #1776197)

Utilizator mariusadamMarius Adam mariusadam Data 10 octombrie 2016 23:59:34
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.32 kb
package com.company;

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) {
            return;
        }
        int i, j, n, m;

        try {
            FileReader reader = new FileReader(this.inputFile);
            Scanner     input = new Scanner(reader);
            n = input.nextInt();
            m = input.nextInt();

            this.graph = new Node[n + 1];
            for(; m > 0; m--) {
                i = input.nextInt();
                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 e) {
            e.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();
    }
}