Pagini recente » Cod sursa (job #1058477) | Monitorul de evaluare | Cod sursa (job #776953) | Cod sursa (job #2437845) | Cod sursa (job #1748818)
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.*;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new FileInputStream("biconex.in"));
int N = in.nextInt();
int M = in.nextInt();
Graph G = new Graph(N);
for (int i = 0; i < M; i++) {
int x = in.nextInt();
int y = in.nextInt();
G.addEdge(x, y);
G.addEdge(y, x);
}
BiconnectedComponents BC = new BiconnectedComponents(G);
int[][] components = BC.computeBiconnectedComponents();
PrintWriter out = new PrintWriter(new FileOutputStream("biconex.out"));
out.println(components.length);
for (int i = 0; i < components.length; i++) {
for (int j = 0; j < components[i].length; j++) {
out.printf("%d ", components[i][j]);
}
out.println();
}
in.close();
out.close();
}
static class Graph{
private static class Edge{
int node;
int next;
Edge(int node, int next){
this.node = node;
this.next = next;
}
}
final static int NIL = -1;
private int[] head;
private int[] degree;
private ArrayList<Edge> graph;
private int N;
private int counter;
Graph(int N){
initialize(N);
}
public int getN() {
return N;
}
private void initialize(final int N){
head = new int[N];
degree = new int[N];
graph = new ArrayList<>();
this.N = N;
this.counter = 0;
Arrays.fill(head, NIL);
Arrays.fill(degree, 0);
}
void addEdge(int x, int y){
if (!(1 <= x && x <= N)) throw new AssertionError();
x--; y--;
graph.add(new Edge(y, head[x]));
head[x] = counter++;
degree[x]++;
}
int getHead(int node){
if (!(1 <= node && node <= N)) throw new AssertionError();
node--;
return head[node];
}
int getNext(int p){
if (!(0 <= p && p < counter)) throw new AssertionError();
return graph.get(p).next;
}
int getNeighbour(int p){
if (!(0 <= p && p < counter)) throw new AssertionError();
return graph.get(p).node + 1;
}
boolean isEmpty(int node){
if (!(1 <= node && node <= N)) throw new AssertionError();
node--;
return head[node] == NIL;
}
int size(int node){
assert 1 <= node && node <= N;
node--;
return degree[node];
}
Graph transpose(){
Graph GT = new Graph(N);
for (int i = 1; i <= N; i++) {
for (int son : getNeighbours(i))
GT.addEdge(son, i);
}
return GT;
}
List<Integer> getNeighbours(int node){
if (!(1 <= node && node <= N)) throw new AssertionError();
List<Integer> list = new ArrayList<>();
for (int p = head[node - 1]; p != NIL; p = graph.get(p).next) {
list.add(graph.get(p).node + 1);
}
return list;
}
}
static class Pair implements Comparable<Pair>{
int first, second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public int compareTo(Pair o) {
int cmp1 = Integer.compare(first, o.first);
if (cmp1 != 0)
return cmp1;
else
return Integer.compare(second, o.second);
}
}
static class BiconnectedComponents {
private final Graph G;
private final int N;
private final int[] lowIndex, dfn;
private List<Pair> stack;
private final ArrayList<ArrayList<Integer>> components;
private int numberOfBCs;
private final boolean[] articulationPoints;
private final ArrayList<Pair> bridges;
BiconnectedComponents(Graph graph){
this.G = graph;
this.N = G.getN();
lowIndex = new int[N + 1];
dfn = new int[N + 1];
stack = new LinkedList<>();
articulationPoints = new boolean[N + 1];
components = new ArrayList<>();
bridges = new ArrayList<>();
}
private void dfs(int node, int root, int number){
lowIndex[node] = dfn[node] = number;
int numberSons = 0;
boolean isArticulationPoint = false;
for (int p = G.getHead(node); p != Graph.NIL; p = G.getNext(p)){
int son = G.getNeighbour(p);
if (dfn[son] == -1){
numberSons++;
stack.add(new Pair(node, son));
dfs(son, root, number + 1);
lowIndex[node] = Math.min(lowIndex[node], lowIndex[son]);
if (lowIndex[son] >= dfn[node]) { // node is an articulation point
biconex(node, son);
isArticulationPoint = true;
}
if (lowIndex[son] > dfn[node]){
// (node,son) is a bridge
bridges.add(new Pair(Math.min(node, son), Math.max(node, son)));
}
}
else
lowIndex[node] = Math.min(lowIndex[node], dfn[son]);
}
if (isArticulationPoint || (node == root && numberSons > 1)){
articulationPoints[node] = true;
}
}
private void biconex(int node, int son){
components.add(new ArrayList<>());
Pair p = new Pair(node, son);
Pair q;
do {
q = stack.get(stack.size() - 1);
stack.remove(stack.size() - 1);
components.get(numberOfBCs).addAll(Arrays.asList(q.first, q.second));
} while (p.compareTo(q) != 0);
numberOfBCs++;
}
int[][] computeBiconnectedComponents(){
numberOfBCs = 0;
components.clear();
stack.clear();
bridges.clear();
Arrays.fill(dfn, -1);
Arrays.fill(lowIndex, -1);
Arrays.fill(articulationPoints, false);
for (int i = 1; i <= N; i++) {
if (dfn[i] == -1) {
dfs(i, i, 0);
break;
}
}
int[][] comps = new int[numberOfBCs][];
for (int i = 0; i < numberOfBCs; i++) {
Set<Integer> hashSet = new HashSet<>();
components.get(i).forEach(hashSet::add);
ArrayList<Integer> list = new ArrayList<>(hashSet);
list.sort(Integer::compareTo);
comps[i] = new int[list.size()];
for (int j = 0; j < list.size(); j++) {
comps[i][j] = list.get(j);
}
}
return comps;
}
boolean[] getArticulationPoints(){
return articulationPoints;
}
Pair[] getBridges(){
Pair[] bridge = new Pair[bridges.size()];
for (int i = 0; i < bridge.length; i++) {
bridge[i] = bridges.get(i);
}
return bridge;
}
}
}