Pagini recente » Cod sursa (job #695843) | Cod sursa (job #125082) | Cod sursa (job #2743841) | Cod sursa (job #3178718) | Cod sursa (job #2413015)
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.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Stack;
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;
int timp;
@SuppressWarnings("unchecked")
ArrayList<Integer> adj[] = new ArrayList[NMAX];
class Edge {
int x;
int 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<ArrayList<Integer>> result) {
try {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
OUTPUT_FILE)));
pw.printf("%d\n", result.size());
for (ArrayList<Integer> ctc : result) {
for (int nod : ctc) {
pw.printf("%d ", nod);
}
pw.printf("\n");
}
pw.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private ArrayList<ArrayList<Integer>> getResult() {
System.out.println("n = " + n + " si m = " + m);
ArrayList<ArrayList<Integer>> sol = new ArrayList<>();
timp = 0;
Stack<Edge> s = new Stack<>();
int[] idx = new int[n + 1];
int[] low = new int[n + 1];
for(int i = 1; i <= n; i++){
idx[i] = NMAX;
low[i] = NMAX;
}
for(int i = 1; i <= n; i++) {
if(idx[i] == NMAX) {
dfsCV(i, idx, low, true, sol, s);
}
}
return sol;
}
private void dfsCV(int start, int[] idx, int[] low, boolean rad, ArrayList<ArrayList<Integer>> sol, Stack<Edge> s){
idx[start] = timp;
low[start] = timp;
timp++;
HashSet<Integer> copii = new HashSet<>();
for(int neigh : adj[start]){
if(idx[neigh] == NMAX){
Edge edge = new Edge();
edge.x = start;
edge.y = neigh;
s.push(edge);
copii.add(neigh);
dfsCV(neigh, idx, low, false, sol, s);
low[start] = Math.min(low[start], low[neigh]);
}
else {
if(rad)
copii.add(neigh);
low[start] = Math.min(low[start], idx[neigh]);
}
}
if(rad) {
System.out.println("Pentru start = " + start + " avem nr_copii = " + copii.size());
if(copii.size() >= 2) {
for(int i = 1; i <= copii.size(); i++) {
while(!s.isEmpty()) {
Edge ed;
HashSet<Integer> nodes = new HashSet<>();
do {
ed = s.pop();
System.out.println("ed.x = " + ed.x + " si ed.y = " + ed.y);
nodes.add(ed.x);
nodes.add(ed.y);
}
while(ed.x != start);
ArrayList<Integer> ar = new ArrayList<>(nodes);
Collections.sort(ar);
sol.add(ar);
}
}
}
}
else {
for(int neigh : copii){
if(low[neigh] >= idx[start]) {
Edge ed, edge = new Edge();
edge.x = start;
edge.y = neigh;
HashSet<Integer> nodes = new HashSet<>();
System.out.println("Pentru start = " + start + " si neigh = " + neigh + " avem:");
do {
ed = s.pop();
System.out.println("ed.x = " + ed.x + " si ed.y = " + ed.y);
nodes.add(ed.x);
nodes.add(ed.y);
}
while(ed.x != edge.x && ed.y != edge.y);
ArrayList<Integer> ar = new ArrayList<>(nodes);
Collections.sort(ar);
sol.add(ar);
break;
}
}
}
}
public void solve() {
readInput();
writeOutput(getResult());
}
}
public static void main(String[] args) {
new Task().solve();
}
}