#include <stack>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maximum_value_of_f=5001,maximum_value_of_r=20001;
int f,r;
struct every_node_in_the_graph{
	int the_first_subscript_index_of_these_nodes_which_connected_to_this_node_in_the_array,low,dfn;
	every_node_in_the_graph(){
		the_first_subscript_index_of_these_nodes_which_connected_to_this_node_in_the_array=-1;low=dfn=0;}}every_node_in_the_graph[maximum_value_of_f];
struct every_edge_in_the_graph{
	int the_subscript_index_of_the_node_in_this_room,the_subscript_index_of_the_next_edge_in_the_edge_array;
	every_edge_in_the_graph(){
		the_subscript_index_of_the_next_edge_in_the_edge_array=-1;}}every_edge_in_the_graph[maximum_value_of_r];
bool have_these_two_nodes_been_connected[maximum_value_of_f][maximum_value_of_f]={false};
int the_number_of_the_pointer_of_the_edge_array=-1;
void insrt_an_edge(int,int);
int the_index_of_the_time=0;
void an_algorithm_named_tarjan(int,int);
int main(){
	cin>>f>>r;
	int a,b;
	for(int i=1;i<=r;i++){
		cin>>a>>b;
		if(have_these_two_nodes_been_connected[a][b])
			continue;
		insrt_an_edge(a,b);
		insrt_an_edge(b,a);
		have_these_two_nodes_been_connected[a][b]=have_these_two_nodes_been_connected[b][a]=true;}
	an_algorithm_named_tarjan(1,-1);
	int the_number_of_these_nodes_degree[maximum_value_of_f]={0},the_last_number_we_need_to_output=0;
	for(int i=1;i<=f;i++)
		for(int j=every_node_in_the_graph[i].the_first_subscript_index_of_these_nodes_which_connected_to_this_node_in_the_array;j!=-1;j=every_edge_in_the_graph[j].the_subscript_index_of_the_next_edge_in_the_edge_array)
			if(every_node_in_the_graph[i].low!=every_node_in_the_graph[every_edge_in_the_graph[j].the_subscript_index_of_the_node_in_this_room].low)
				the_number_of_these_nodes_degree[every_node_in_the_graph[i].low]++;
	for(int i=1;i<=f;i++)
		if(the_number_of_these_nodes_degree[i]==1)
			the_last_number_we_need_to_output++;
	cout<<(the_last_number_we_need_to_output+1)/2<<endl;
	return 0;}
void insrt_an_edge(int the_beginning_of_an_edge_needed_inserting,int the_ending_of_an_edge_needed_inserting){
	the_number_of_the_pointer_of_the_edge_array++;
	every_edge_in_the_graph[the_number_of_the_pointer_of_the_edge_array].the_subscript_index_of_the_node_in_this_room=the_ending_of_an_edge_needed_inserting;
	every_edge_in_the_graph[the_number_of_the_pointer_of_the_edge_array].the_subscript_index_of_the_next_edge_in_the_edge_array=every_node_in_the_graph[the_beginning_of_an_edge_needed_inserting].the_first_subscript_index_of_these_nodes_which_connected_to_this_node_in_the_array;
	every_node_in_the_graph[the_beginning_of_an_edge_needed_inserting].the_first_subscript_index_of_these_nodes_which_connected_to_this_node_in_the_array=the_number_of_the_pointer_of_the_edge_array;
	return;}
void an_algorithm_named_tarjan(int u,int the_node_which_leads_this_node_to_be_done){
	int v;
	every_node_in_the_graph[u].low=every_node_in_the_graph[u].dfn=++the_index_of_the_time;
	for(int i=every_node_in_the_graph[u].the_first_subscript_index_of_these_nodes_which_connected_to_this_node_in_the_array;i!=-1;i=every_edge_in_the_graph[i].the_subscript_index_of_the_next_edge_in_the_edge_array){
		v=every_edge_in_the_graph[i].the_subscript_index_of_the_node_in_this_room;
		if(!every_node_in_the_graph[v].dfn){
			an_algorithm_named_tarjan(v,u);
			every_node_in_the_graph[u].low=min(every_node_in_the_graph[u].low,every_node_in_the_graph[v].low);}
		else
			if(v!=the_node_which_leads_this_node_to_be_done)
				every_node_in_the_graph[u].low=min(every_node_in_the_graph[u].low,every_node_in_the_graph[v].dfn);}
	return;}

• Re:3177 tarjan 水过 (3799) shenghuXu 2023-04-30 15:31:45