Pagini recente » Cod sursa (job #2879989) | Cod sursa (job #2223135) | Cod sursa (job #2875585) | Cod sursa (job #2052442) | Cod sursa (job #2609745)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Stack;
import java.util.TreeSet;
import java.util.ArrayList;
public class Main {
static class Task {
public static final String INPUT_FILE = "biconex.in";
public static final String OUTPUT_FILE = "biconex.out";
public static final int NMAX = 100005; // 10^5
int n;
int m;
@SuppressWarnings("unchecked")
ArrayList<Integer> adj[] = new ArrayList[NMAX];
class Edge {
int x;
int y;
public Edge(int x, int y) {
super();
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Edge [x=" + x + ", y=" + y + "]";
}
}
private void readInput() {
try {
BufferedReader br = new BufferedReader(new FileReader(
INPUT_FILE));
String line = br.readLine();
String[] fields = line.split(" ");
n = Integer.parseInt(fields[0]);
m = Integer.parseInt(fields[1]);
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}
for (int i = 1; i <= m; i++) {
int x, y;
line = br.readLine();
fields = line.split(" ");
x = Integer.parseInt(fields[0]);
y = Integer.parseInt(fields[1]);
adj[x].add(y);
}
br.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private void writeOutput(ArrayList<TreeSet<Integer>> result) {
try {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
OUTPUT_FILE)));
pw.printf("%d\n", result.size());
for(int i = 0; i <= result.size() - 1; i++) {
TreeSet<Integer> comp = result.get(i);
while (comp.size() > 1) {
int n = comp.pollFirst();
pw.printf("%d ", n);
}
if(comp.size() == 1) {
int n = comp.pollFirst();
pw.printf("%d", n);
}
pw.println();
}
pw.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private ArrayList<TreeSet<Integer>> getResult() {
ArrayList<TreeSet<Integer>> sol = new ArrayList<>();
int timp = 0;
int idx[] = new int[n+1];
int low[] = new int[n+1];
int parent[] = new int[n+1];
for(int i = 0; i <= n; i++) {
idx[i] = -1;
low[i] = -1;
}
Stack<Edge> stack = new Stack<Edge>();
for(int v = 1; v <= n; v++) {
if(idx[v] == -1) {
timp = dfsBC(sol, stack, timp, parent, low, idx, v);
TreeSet<Integer> sortedSet = new TreeSet<Integer>();
while(!stack.isEmpty()) {
Edge e = stack.pop();
sortedSet.add(e.x);
sortedSet.add(e.y);
}
sol.add(sortedSet);
}
}
return sol;
}
public int dfsBC(ArrayList<TreeSet<Integer>> sol, Stack<Edge> stack, int timp, int[] parent, int[] low, int[] idx, int v) {
idx[v] = timp;
low[v] = timp;
timp++;
ArrayList<Integer> childs = new ArrayList<Integer>();
for(int i = 0; i <= adj[v].size() - 1; i++) {
int u = adj[v].get(i);
// daca u nu este parintele lui v
if(parent[v] != u) {
// daca nodul este nevizitat
if(idx[u] == -1) {
stack.push(new Edge(v, u));
childs.add(u);
parent[u] = v;
timp = dfsBC(sol, stack, timp, parent, low, idx, u);
low[v] = Integer.min(low[v], low[u]);
}
else {
stack.push(new Edge(v, u));
// nodul u este descoperit, verificam daca gasim o scurtatura catre un stramos
low[v] = Integer.min(low[v], idx[u]);
}
}
}
// v este punct de articulatie daca:
if(parent[v] == 0) {
// v este radacina arborelui de adancime si v are doi sau mai multi copii
if(childs.size() >= 2) {
TreeSet<Integer> sortedSet = new TreeSet<Integer>();
while(stack.peek().x != v) {
Edge e = stack.pop();
sortedSet.add(e.x);
sortedSet.add(e.y);
}
Edge e = stack.pop();
sortedSet.add(e.x);
sortedSet.add(e.y);
sol.add(sortedSet);
}
} else {
// v nu este radacina arborelui de adancime şi are un copil u in arbore,
// astfel incat niciun nod din subarborele dominat de u
// nu este conectat cu un stramos al lui v printr-o muchie inapoi
// (copii lui nu pot ajunge pe alta cale pe un nivel superior
// in arborele de adancime)
int ok = 0;
for(int i = 0; i <= childs.size() - 1; i++) {
int u = childs.get(i);
if(low[u] >= idx[v]) {
ok = 1;
break;
}
}
if(ok == 1) {
TreeSet<Integer> sortedSet = new TreeSet<Integer>();
while(stack.peek().x != v) {
Edge e = stack.pop();
sortedSet.add(e.x);
sortedSet.add(e.y);
}
Edge e = stack.pop();
sortedSet.add(e.x);
sortedSet.add(e.y);
sol.add(sortedSet);
}
}
return timp;
}
public void solve() {
readInput();
writeOutput(getResult());
}
}
public static void main(String[] args) {
new Task().solve();
}
}