Pagini recente » Cod sursa (job #893568) | Cod sursa (job #2774328) | Cod sursa (job #6446) | Cod sursa (job #778040) | Cod sursa (job #2602418)
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.*;
public class Biconex {
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;
public static int time = 0;
int n;
int m;
int [] disc;
int [] low;
@SuppressWarnings("unchecked")
ArrayList<Integer> adj[] = new ArrayList[NMAX];
ArrayList<ArrayList<Integer>> sol = new ArrayList<>();
Stack<Integer> st = new Stack<>();
private void readInput() {
try {
Scanner sc = new Scanner(new BufferedReader(new FileReader(
INPUT_FILE)));
n = sc.nextInt();
m = sc.nextInt();
disc = new int[n + 1];
low = new int[n + 1];
Arrays.fill(disc, -1);
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<ArrayList<Integer>> result) {
try {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
OUTPUT_FILE)));
pw.printf("%d\n", result.size());
for (ArrayList<Integer> bic : result) {
for (int nod : bic) {
pw.printf("%d ", nod);
}
pw.printf("\n");
}
pw.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private void dfs(int src, int dad) {
disc[src] = low[src] = disc[dad] + 1;
st.push(src);
for (Integer it : adj[src]) {
if (disc[it] == -1) {
dfs(it, src);
low[src] = Math.min(low[src], low[it]);
if (low[it] >= disc[src]) {
ArrayList<Integer> biconnectedComp = new ArrayList();
int node;
do {
biconnectedComp.add(node = st.peek());
st.pop();
} while(it != node);
biconnectedComp.add(src);
sol.add(biconnectedComp);
}
} else if (it != dad){
low[src] = Math.min(low[src], disc[it]);
}
}
}
private ArrayList<ArrayList<Integer>> getResult() {
// TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
// de adiacenta in adj.
dfs(1, 0);
return sol;
}
public void solve() {
readInput();
writeOutput(getResult());
}
}
public static void main(String[] args) {
new Task().solve();
}
}