Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:3177 tarjan 水过In Reply To:3177 tarjan 水过 Posted by:c20161007 at 2016-07-19 21:45:51 > #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;} Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator