Pagini recente » Cod sursa (job #3245982) | Cod sursa (job #2919307) | Cod sursa (job #1739222) | Cod sursa (job #3158702) | Cod sursa (job #1422893)
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();
}
}