Pagini recente » Cod sursa (job #626549) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #2378032) | Cod sursa (job #3032866) | Cod sursa (job #2199050)
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.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.Scanner;
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;
Edge(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return x + " " + y;
}
}
private void readInput() {
try {
Scanner sc = new Scanner(new BufferedReader(new FileReader(
INPUT_FILE)));
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++)
adj[i] = new ArrayList<>();
for (int i = 1; i <= m; i++) {
int x, y;
x = sc.nextInt();
y = sc.nextInt();
adj[x].add(y);
adj[y].add(x);
}
sc.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private void writeOutput(ArrayList<HashSet<Integer>> result) {
try {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
OUTPUT_FILE)));
pw.printf("%d\n", result.size());
for (HashSet<Integer> ctc : result) {
for (int nod : ctc) {
pw.printf("%d ", nod);
}
pw.printf("\n");
}
pw.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private void dfsCV(int v, int[] idx, int[] low, int timp, Deque<Edge> stack, ArrayList<Deque<Integer>> kids, ArrayList<HashSet<Integer>> sol) {
idx[v] = timp;
low[v] = timp;
timp++;
for (Integer u : adj[v]) {
stack.push(new Edge(v, u));
if (idx[u] == 0) {
kids.get(v - 1).push(u);
dfsCV(u, idx, low, timp, stack, kids, sol);
low[v] = Math.min(low[v], low[u]);
} else {
low[v] = Math.min(low[v], idx[u]);
}
}
if (v == 1) {
if (kids.get(v - 1).size() >= 2) {
for (Integer k : kids.get(v - 1)) {
HashSet<Integer> aux = new HashSet<>();
Edge edge = new Edge(-1, -1);
while (edge.x != v || edge.y != k) {
edge = stack.remove();
aux.add(edge.x);
aux.add(edge.y);
}
sol.add(aux);
}
}
} else {
for (Integer u : kids.get(v - 1)) {
if (low[u] >= idx[v]) {
HashSet<Integer> aux = new HashSet<>();
Edge edge = new Edge(-1, -1);
while (edge.x != v || edge.y != u) {
edge = stack.remove();
aux.add(edge.x);
aux.add(edge.y);
}
sol.add(aux);
}
}
}
}
private ArrayList<HashSet<Integer>> getResult() {
// TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
// de adiacenta in adj.
ArrayList<HashSet<Integer>> sol = new ArrayList<>();
int timp = 1;
int idx[] = new int[n + 1];
int low[] = new int[n + 1];
Deque<Edge> stack = new ArrayDeque<Edge>();
ArrayList<Deque<Integer>> kids = new ArrayList<>();
for (int v = 1; v <= n; v++) {
kids.add(new ArrayDeque<Integer>());
}
for (int v = 1; v <= n; v++) {
if (idx[v] == 0) {
dfsCV(v, idx, low, timp, stack, kids, sol);
}
}
return sol;
}
public void solve() {
readInput();
writeOutput(getResult());
}
}
public static void main(String[] args) {
new Task().solve();
}
}