import java util Scanner import java util ArrayList class Vertex priva

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import java.util.Scanner;
import java.util.ArrayList;
class Vertex{
private int mark, size, comp;
private ArrayList<Integer> value = new ArrayList<Integer>();
Vertex(){
this.mark = 0; //метка посещений вершины visitvertex'ом
this.size = 0; //размер arraylist'а инцидентных
this.comp = -1; //тот самый comp,о котором я говорил в своем коде. указывает на компоненту,в которой находится эта вершина
}
/* НАХУЙ НЕ НАДО
void prisvaivanie(int x) {
this.value.add(x);
this.size++;
}
public int getMark(){
return this.mark;
}
public int getSize(){
return this.size;
}
public int getValue(int i){
return this.value.get(i);
}
public int getComp(){
return this.comp;
}
void pointMark(){
this.mark = 1;
}
public void setComp(int comp) {
this.comp = comp;
}
*/
}
//очередь
class Queue{
private int head, tail;
private ArrayList<Integer> data;
Queue(){
this.data = new ArrayList<Integer>();
this.head = 0;
this.tail = 0;
}
boolean QueueEmpty(){
return this.tail == this.head;
}
int Dequeue(){
int x = this.data.get(this.head);
this.head++;
if(this.tail == this.head){
this.tail = 0;
this.head = 0;
}
return x;
}
void Enqueue(int x){
this.data.add(this.tail, x);
this.tail++;
}
}
public class BridgeNum {
public static void dfs(Vertex[] graph, Queue queue, int[] parents, int n){ // влад чуть отошел от лекций,он напихал в dfs'ы часть visitvertex'ов и запускал dfs'ы рекурсивно
int i, size = graph[n].getSize(); //но по сути тут все то же самое.Вершина, в которую попали,помещается в очередь,запускается dfs для всех инцидентных вершин,в которых мы еще не были.
graph[n].pointMark();//равносильно записи graph[n].mark=1 (помечает вершину)
queue.Enqueue(n);
for(i = 0; i < size; i++){
int help = graph[n].getValue(i);//равносильно записи help=graph[n].get.value(i) (обращение к i=тому элементу инцидентных вершин)
if(graph[help].getMark() == 0){
parents[help] = n;
dfs(graph, queue, parents, help);
}
}
}
public static int dfs2(Vertex[] temp, Queue queue, int[] parents, int component){ //по лекциям
int v;
while(queue.QueueEmpty() == false) {
v = queue.Dequeue();
if(temp[v].getComp() == -1){ //тут у меня и написан unsorted потому-что данные по тому,какой именно компоненте принадлежит вершина не используются,только то,принадлежит ли.
VisitVertex(temp, parents, v, component);
component++;
}
}
return component;
}
public static void VisitVertex(Vertex[] temp/*здесь*/, int[] parents, int v, int component){
int i, help, size = temp[v].getSize();
temp[v].setComp(component);//temp элемент смотри двумя строчками выше. temp-массив vertex'ов,равносильно записи graph[v].setcomp в main'е
for(i = 0; i < size; i++){
help = temp[v].getValue(i);
if(temp[help].getComp() == -1 && parents[help] != v) VisitVertex(temp, parents, help, component);
}
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int i, x, y, component = 1, n = in.nextInt(), m = in.nextInt();
Vertex[] graph = new Vertex[n];
Queue queue = new Queue();
int[] parents = new int[n];
for(i = 0; i < n; i++){
graph[i] = new Vertex();
parents[i] = n+1;
}
for(i = 0; i < m; i++){
x = in.nextInt();
y = in.nextInt();
graph[x].prisvaivanie(y);
graph[y].prisvaivanie(x);
}
for(i = 0; i < n; i++){
if(graph[i].getMark() == 0){
component--;
dfs(graph, queue, parents, i);
}
component = dfs2(graph, queue, parents, component);
}
System.out.println(component-1);
}
}