import java util ArrayList import java util Arrays import java util Sc

  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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.lang.Math;
class point {
int mark=0; //метка занятости
int parent=-1; //корень
int cap=0; //число инцидентных ребер
ArrayList<Integer> list = new ArrayList<Integer>();
}
//кольцевой буфер
class Queue {
int size,head,tail;
int[] data;
Queue(int size) {
data = new int [this.size = size];
}
void add(int value) {
if (++tail == size)
tail = 0;
data[tail] = value;
}
int extract() {
if (++head == size)
head = 0;
return data[head];
}
}
public class BridgeNum {
public static void main(String[] arg) {
Scanner sc = new Scanner(System.in);
int i=0,j=0,n=sc.nextInt(),m=sc.nextInt(),first,second,CompNumber=1;
point [] graph=new point[n];
int [] unsorted=new int [n];
for (i=0;i<n;i++) {
graph[i]=new point();
graph[i].mark=0;
unsorted[i]=i;
}
Queue q=new Queue(n+1);
for(i=0;i<m;i++){
first=sc.nextInt(); second=sc.nextInt();
graph[first].cap++;
graph[first].list.add(second);
graph[second].cap++;
graph[second].list.add(first);
}
for (i=0;i<n;i++) {
if (graph[i].mark == 0) {
CompNumber--;
VisitVertex1(graph, q, i);
}
while (q.head != q.tail)//dfs2
{
first = q.extract();
if (unsorted[first] == first) {
unsorted[first]=-1;
VisitVertex2(graph, q, first, unsorted);
CompNumber++;
}
}
}
System.out.println(CompNumber-1);
}
public static void VisitVertex1(point[] graph, Queue q,int n)
{
int timelimit1,timelimit2;
graph[n].mark=1; //gray
q.add(n);//Enq
timelimit1=graph[n].cap;
for(int i=0;i<timelimit1;i++)
{
timelimit2=graph[n].list.get(i);
if(graph[timelimit2].mark==0)
{
graph[timelimit2].parent=n;
VisitVertex1(graph,q,graph[n].list.get(i));
}
}
graph[n].mark=2;//black
}
public static void VisitVertex2(point[] graph, Queue q,int f,int[] unsorted)
{
int timelimit1=graph[f].cap;
unsorted[f]=-1;
for(int i=0;i<timelimit1;i++)
{
int timelimit2=graph[f].list.get(i);
if(unsorted[timelimit2]!=-1)
if(graph[timelimit2].parent!=f)
{
VisitVertex2(graph,q,timelimit2,unsorted);
}
}
}
}