Cod sursa(job #1705213)

Utilizator TheDeathEne Bogdan Adrian TheDeath Data 20 mai 2016 02:00:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 4.27 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;




class Graph2 {

	
	public int numNodes;//numarul de noduri din graf
	public int portale;//numarul de portale

	
	public List<List<Integer>> edges;//definim muchiile ca lista de lista unde indicele primei liste este
	//nodul de plecare si indicele celui de-al doilea este nodul spre care se duce
	//initializam lista si adaugam un element pentru ca indicii trebuie sa coincida cu ID nodului
	public Graph2() {
		edges = new ArrayList<>();
		edges.add(new ArrayList<Integer>());
	}
	
	//functie ce insereaza cate un arraylist pentru fiecare nod
	public void insertNode() {
		edges.add(new ArrayList<Integer>());
	}
	

	
	//functie ce ne insereaza muchia efectiv
	public void insertEdge(int fromNodeIdx, int toNodeIdx) {
		edges.get(fromNodeIdx).add(toNodeIdx);
	}
//functie pentru citirea fisierului de intrare si parsarea acestuia in variabilele si listele create
	public void readData(BufferedReader input) throws IOException {
		StringTokenizer tokenizer;
		String read = input.readLine();
		tokenizer = new StringTokenizer(read, " ");
		numNodes = Integer.parseInt(tokenizer.nextToken());
		portale = Integer.parseInt(tokenizer.nextToken());

		//inseram cate o lista pentru fiecare nod
		for (int i = 1; i <= numNodes; i++) {
			insertNode();
		}

		for (int edgeIdx = 1; edgeIdx <= portale; edgeIdx++) {
			read = input.readLine();
			tokenizer = new StringTokenizer(read, " ");
			
			int node1 = Integer.parseInt(tokenizer.nextToken());
			int node2 = Integer.parseInt(tokenizer.nextToken());
			//muchia o inseram in ambele directii deoarece la inceput este neorientat
			insertEdge(node2, node1);
			insertEdge(node1, node2);
			
		}
		

	}
	
	@Override //functie de test pentru a vedea graful
	public String toString() {

		StringBuilder sb = new StringBuilder("Print Graph:\n");

		for(int n = 1; n <= numNodes; n++) {
			sb.append("OutEdges for " + n + " -> ");

			for (Integer edge : edges.get(n)) {
				sb.append(edge);
                sb.append(" | ");
			}

			sb.append("\n");
		}
		sb.append("\n");

		return sb.toString();

	}
}
class DFSi {
	int numNodes, componente, u;
	String[] c;//vector pentru culoarea nodului
	Graph2 g;//referinta la graph
	Boolean cycle;//true pentru ciclu si false daca nu e ciclu

	public DFSi(int numNodes, Graph2 g) {
		this.numNodes = numNodes;
		this.g = g;
		c = new String[numNodes + 1];
		

	}
	//functie dfs care imi calculeaza numarul de noduri parcurse
	public int doDFS() {

		Arrays.fill(c, "alb");//umplem tot vectorul cu alb
		Stack<Integer> stack = new Stack<Integer>();//initializam o stiva
		//parcurgem absolut toate nodurile
		for (int i = 1; i <= numNodes; i++) {
			//verificam daca nodul e alb si il adaugam in stiva 
			if (c[i].equals("alb")) {
				componente++;
				stack.push(i);
				
				c[i] = "gri";//facem nodul gri, e in curs de procesare
			}
			//cat timp sunt elemente in stiva ne aflam pe o componenta conexa din graf
			while (!stack.isEmpty()) {
				u = stack.pop();//scoatem varful stivei
				c[u] = "negru";//cand scoatem nodul din stiva acesta devine negru(terminat)
				//parcurgem toti vecini nodului extras
				for (Integer node : g.edges.get(u)) {
					if (c[node].equals("alb")) {
						c[node] = "gri";
						
						stack.push(node);
					} 
				}

			}
			
			

		}
	return componente;

	}

}

public class Main {
public static void main(String[] args) throws IOException {
		
		BufferedReader input = new BufferedReader(new FileReader("dfs.in"));//deschidem fisierul pentru citire
		BufferedWriter output = new BufferedWriter(new FileWriter("dfs.out"));//deschidem fisierul pentru scriere
		
		Graph2 g = new Graph2();//creem un obiect graph
		g.readData(input);//citim datele cu functia readdata
		DFSi dfs = new DFSi(g.numNodes,g);//creem un obiect dfs
		//scriem in fisierul de iesire rezultatul functiei doDfs
		output.write(dfs.doDFS()+"\n");
		//inchidem fisierele de intrare si de iesire
		input.close();
		output.close();
	}
}