Pagini recente » Cod sursa (job #646690) | Cod sursa (job #1131473) | tema | Cod sursa (job #981895) | Cod sursa (job #1705406)
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.util.Stack;
import java.util.LinkedList;
class List {
public LinkedList<Integer> neighbors;
List(int n) {
neighbors = new LinkedList<Integer>();
}
}
class Pair {
int node1;
int node2;
public Pair(int node1, int node2) {
this.node1 = node1;
this.node2 = node2;
}
}
public class Main {
private static int N, M, node1, node2;
private static List adjList[];
private static int parent[];
private static int nrConnex = 0;
private static int visited[];
private static void readData() throws IOException {
BufferedReader bf = new BufferedReader(new FileReader("dfs.in"));
String tmp[] = bf.readLine().split(" ");
N = Integer.parseInt(tmp[0]);
M = Integer.parseInt(tmp[1]);
// System.out.println("N: " + N);
// System.out.println("M: " + M);
//initializare vector de parinti
parent = new int[N + 1];
for(int i = 1; i <= N; i ++) {
parent[i] = 0;
}
//initializare vector de adiacenta
adjList = new List[N + 1];
for(int i = 1; i <= N; i ++) {
adjList[i] = new List(N);
}
//initalizare vector de vizitari
//negru = 2; gri = 1; alb = 0
visited = new int[N + 1];
for(int i = 1; i <= N; i ++) {
visited[i] = 0;
}
for(int i = 0; i < M; i ++) {
tmp = bf.readLine().split(" ");
node1 = Integer.parseInt(tmp[0]);
node2 = Integer.parseInt(tmp[1]);
// System.out.println("node1: " + node1);
// System.out.println("node2: " + node2);
Pair p = new Pair(node1, node2);
adjList[p.node1].neighbors.add(p.node2);
adjList[p.node2].neighbors.add(p.node1);
}
// System.out.println("Afisare vector de adiacenta: ");
// for(int i = 1; i <=N; i ++) {
// System.out.println(adjList[i].neighbors);
// }
}
private static int DFS() {
for(int i = 1; i <= N; i ++) {
//daca nu a fost vizitat
if(visited[i] == 0) {
explore(i);
nrConnex ++;
}
}
return nrConnex;
}
private static void explore(int node) {
//il fac gri
visited[node] = 1;
//pentru fiecare copil al sau
Iterator<Integer> it = adjList[node].neighbors.listIterator();
while(it.hasNext()) {
int number = it.next();
//daca este alb, ii marcam parintele si exploram noii copii
if(visited[number] == 0) {
parent[number] = node;
explore(number);
}
}
//il facem negru
visited[node] = 2;
}
public static void main(String[] args) throws IOException {
readData();
int nr = DFS();
PrintWriter pw = new PrintWriter("dfs.out");
pw.println(nr);
pw.close();
//System.out.println("Avem " + nr + " componente conexe");
}
}