Cod sursa(job #1450895)

Utilizator RuxyRezidentTMRuxandra P RuxyRezidentTM Data 15 iunie 2015 00:36:16
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.97 kb
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

class DFS {
	
	
	BufferedReader in;
	PrintWriter out;
	
	int m, n;
	ArrayList<ArrayList<Integer>> graph;
	boolean[] visited;
	public void read() throws IOException {
		in = new BufferedReader(new InputStreamReader(new FileInputStream("dfs.in")));
		Scanner inInt = new Scanner(in);
		n = inInt.nextInt();
		m = inInt.nextInt();
		graph = new ArrayList<ArrayList<Integer>>(n+1);
		visited = new boolean[n+1];
		for(int i = 0; i <= n; i++) {
			graph.add(i, new ArrayList<Integer>());
		}
		int x, y;
		for(int i = 0; i < m; i++) {
			x = inInt.nextInt();
			y = inInt.nextInt();
			graph.get(x).add(y);
			graph.get(y).add(x);
			
		}
		inInt.close();
		in.close();
		
		
	
	}
	
	public void write(int components) throws FileNotFoundException {
		out = new PrintWriter(new FileOutputStream ("dfs.out"));
		/*out.println(n + " " + m);
		for(int i = 1; i <= n; i++) {
			ArrayList<Integer> list = graph.get(i);
			for(int j = 0; j < list.size(); j++) {
				out.println(i + " " + list.get(j));		
			}
			
		}*/
		out.println(components);
		out.close();
		
	}
	
	public void myDFS(int x) {
		
		visited[x] = true;
		ArrayList<Integer> list = graph.get(x);
		for(int i = 0; i < list.size(); i++) {
			
			if(visited[list.get(i)] == false) {
				myDFS(list.get(i));
			}
				
			
		}
		
		
	}
	
	public int components() {
		int  p = 0;
		for(int i = 1; i <= n; i++) {
			if(visited[i] == false) {
				p++;
				myDFS(i);
			}
		}
		return p;
	}
	
	
	public static void main(String args[]) {
		
		try {
		DFS dfs = new DFS();
		dfs.read();
		dfs.write(dfs.components());
		
		
		
		} catch(IOException e) {
			e.printStackTrace();
		}
		
		
	}

}