Pagini recente » Cod sursa (job #2690370) | Cod sursa (job #2721894) | Cod sursa (job #2841968) | Cod sursa (job #425971) | Cod sursa (job #2405960)
package bonus;
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.Set;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
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];
int time;
int idx[];
int low[];
List<Edge> s = new ArrayList<>();
ArrayList<ArrayList<Integer>> sol = new ArrayList<>();
class Edge {
int x;
int y;
public Edge(int x, int y) {
this.x = x;
this.y = 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);
}
}
public void push(Edge e) {
s.add(e);
}
public Edge pop() {
return s.remove(s.size() - 1);
}
public int min(int x, int y) {
return x < y ? x : y;
}
public boolean isRoot(int v) {
return v == 1;
}
public ArrayList<Integer> generateNewSol(Edge edge) {
System.out.println("Generete with stack size: " + s.size());
Set<Integer> set = new HashSet<Integer>();
ArrayList<Integer> newSol;
while (!s.isEmpty()) {
Edge e = pop();
set.add(e.x);
set.add(e.y);
if (e.x == edge.x && e.y == edge.y) {
break;
}
}
newSol = new ArrayList<>(set);
System.out.println("New sol size: " + newSol.size());
return newSol;
}
public void cutVertex() {
time = 0;
s = new ArrayList<>();
for (int v = 1; v <= n; ++v) {
if (idx[v] == -1) {
dfsCV(v, 0);
}
}
}
public void dfsCV(int v, int parent) {
idx[v] = time;
low[v] = time++;
//push(v);
List<Integer> children = new ArrayList<>();
for (int u : adj[v]) {
if (u == parent) {
continue;
}
if (idx[u] == -1) {
push(new Edge(v, u));
System.out.println(v + " " + u);
children.add(u);
dfsCV(u, v);
low[v] = min(low[v], low[u]);
if (low[u] >= idx[v]) {
System.out.println("New biconex " + v + " " + u);
sol.add(generateNewSol(new Edge(v, u)));
}
} else {
low[v] = min(low[v], idx[u]);
}
System.out.println(v + " " + idx[v] + " " + u + " " + low[u]);
}
}
private ArrayList<ArrayList<Integer>> getResult() {
// TODO: Gasiti nodurile critice ale grafului neorientat stocat cu liste
// de adiacenta in adj.
low = new int[n + 1];
idx = new int[n + 1];
for (int i = 0; i <= n; ++i) {
idx[i] = -1;
}
cutVertex();
return sol;
}
public void solve() {
readInput();
writeOutput(getResult());
}
}
public static void main(String[] args) {
new Task().solve();
}
}