Cod sursa(job #1422893)

Utilizator bugyBogdan Vlad bugy Data 20 aprilie 2015 10:37:06
Problema Componente biconexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.11 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.HashSet;
import java.util.Set;
import java.util.Stack;

class Muchie {
	int a;
	int b;
	
	public Muchie(int a, int b) {
		this.a = a;
		this.b = b;
	}
}

class Node {

	int id;
	ArrayList<Node> muchii;
	ArrayList<Node> copii;
	
	public Node(int id) {
		this.id = id;
		muchii = new ArrayList<Node>();
		copii = new ArrayList<Node>();
	}
	
	public void addMuchie(Node x) {
		muchii.add(x);
	}
	
	public void addCopil(Node copil) {
		copii.add(copil);
	}
}

class Graf {
	
	ArrayList<Node> noduri;
	
	
	public Graf() {
		noduri = new ArrayList<Node>();
	}
	
	public void addNode(Node x) {
		noduri.add(x);
	}
	
	public Node getNodefromId(int id) {
		return noduri.get(id);
	}
	
}

public class Main {
	
	static int[] idx, low;
	static int timp = 1;
	static int comp = 0;
	public static Stack<Muchie> stack = new Stack<Muchie>();
	public static ArrayList<Set<Integer>> componenta = new ArrayList<Set<Integer>>();
	
	public static int min(int a, int b) {
		if (a < b) {
			return a;
		}
		return b;
	}
	
	public static void dfs (Node x) {
		
		idx[x.id] = timp;
		low[x.id] = timp;
		timp ++;
		
		Node vecin;
		for (int i = 0; i < x.muchii.size(); i++) {
			stack.push(new Muchie(x.id, x.muchii.get(i).id));
			vecin = x.muchii.get(i);
			if (idx[vecin.id] == 0) {
				x.addCopil(vecin);
				dfs(vecin);
				low[x.id] = min(low[x.id],low[vecin.id]);
			} else {
				low[x.id] = min(low[x.id], idx[vecin.id]);
			}
		}
		
		if (x.id == 0 && x.copii.size() > 1) {
			//System.out.println("Punct de articulatie" + (x.id+1));
			Muchie m;
			comp ++;
			
			componenta.add(new HashSet<Integer>());
			while (!stack.empty()) {
				m = stack.pop();
				componenta.get(comp-1).add(m.a + 1);
				componenta.get(comp-1).add(m.b + 1);
				//System.out.println("Comp " + comp + " fac parte " + (m.a + 1) + " " + (m.b + 1));
				for (int i = 0; i < x.copii.size(); i++) {
					if (m.a == x.id && m.b == x.copii.get(i).id) {
						comp ++;
						componenta.add(new HashSet<Integer>());
						//System.out.println("Comp " + comp + " fac parte " + (m.a + 1) + " " + (m.b + 1));
						break;
					}
				}
			}
		} else if (x.id != 1){
			for (int i = 0; i < x.copii.size(); i++) {
				if (low[x.copii.get(i).id] >= idx[x.id]) {
					//System.out.println("Punct de articulatie" + (x.id+1));
					componenta.add(new HashSet<Integer>());
					comp ++;
					Muchie m;
					while (true) {
						m = stack.pop();
						componenta.get(comp-1).add(m.a + 1);
						componenta.get(comp-1).add(m.b + 1);
						//System.out.println("Comp " + comp + " fac parte " + (m.a + 1) + " " + (m.b + 1));
						if (m.a == x.id && m.b == x.copii.get(i).id) {
							break;
						}
					}
					break;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader buffer = new BufferedReader(new FileReader("biconex.in"));
		
		String[] s = buffer.readLine().split(" ");
		int N = Integer.parseInt(s[0]);
		int M = Integer.parseInt(s[1]);
		int x, y;
		Graf graf = new Graf();
		idx = new int[N+1];
		low = new int[N+1];
		
		for (int i = 0; i < N; i++) {
			graf.addNode(new Node(i));
		}
		
		for (int i = 0; i < M; i++) {
			s = buffer.readLine().split(" ");
			x = Integer.parseInt(s[0]);
			y = Integer.parseInt(s[1]);
			graf.getNodefromId(x-1).addMuchie(graf.getNodefromId(y-1));
			graf.getNodefromId(y-1).addMuchie(graf.getNodefromId(x-1));
		}
		buffer.close();
		
		timp = 1;
		
		for (int i = 0; i < N; i++) {
			if (idx[i] == 0) {
				dfs(graf.noduri.get(i));
			}
		}
		BufferedWriter bufferW = new BufferedWriter(new FileWriter("biconex.out"));
		bufferW.write(Integer.toString(comp-1));
		bufferW.write("\n");
		for (int i = 0; i < componenta.size(); i++) {
			Set<Integer> c = componenta.get(i);
			for (Integer nod : c) {
				bufferW.write(Integer.toString(nod)+" ");
			}
			bufferW.write("\n");
		}
		bufferW.close();
	}
}