fork(6) download
copy 
  1. /* ############################################################################
  2.  * START OF HEADER 
  3.  * ############################################################################
  4.  */
  5. #include<cstdio>
  6. #include<cstdio>
  7. #include<iostream>
  8. #include<cstring>
  9. #include<string>
  10. #include<cstdlib>
  11. #include<cmath>
  12. #include<cassert>
  13. #include<ctime>
  14. #include<algorithm>
  15. #include<vector>
  16. #include<stack>
  17. #include<queue>
  18. #include<deque>
  19. #include<list>
  20. #include<set>
  21. #include<map>
  22. using namespace std;
  23.  
  24. #define LL long long
  25. #define LD long double
  26.  
  27. #define sc(x)  scanf("%c",&x) //char
  28. #define si(x)  scanf("%d",&x) //int
  29. #define sf(x)  scanf("%f",&x) //float
  30. #define sl(x)  scanf("%I64d",&x) //int64_
  31. #define sd(x)  scanf("%lf",&x) //double
  32. #define sld(x) scanf("%Lf",&x) //long double
  33. #define slld(x) scanf("%lld",&x) //long long int
  34. #define ss(x)  scanf("%s",x) // string
  35.  
  36. #define pc(x)  printf("%c",x)
  37. #define pi(x)  printf("%d ",x)
  38. #define pf(x)  printf("%f ",x)
  39. #define pl(x)  printf("%I64d ",x)
  40. #define pd(x)  printf("%lf ",x)
  41. #define pld(x) printf("%Lf ",x)
  42. #define plldn(x) printf("%lldn", x);
  43. #define ps(x) printf("%s", x);
  44.  
  45. #define pin(x)  printf("%d\n",x)
  46. #define pln(x)  printf("%I64d\n",x)
  47. #define pfn(x)  printf("%f\n",x)
  48. #define pdn(x)  printf("%lf\n",x)
  49. #define pldn(x) printf("%Lf\n",x)
  50. #define plld(x) printf("%lld\n", x);
  51. #define psn(x)  printf("%s\n",x)
  52.  
  53. #define pn() printf("\n")
  54. #define _p() printf(" ")
  55.  
  56. #define MODVAL 1000000007
  57.  
  58. #define FORab(i,a,b) for(int i=a;i<=b;i++)
  59. #define REVab(i,a,b) for(int i=a;i>=b;i--)
  60. #define FORn(i,n) for(i=0;i<n;i++)
  61. #define REVn(i,n) for(int i=n;i>=0;i--)
  62. #define FORSTL(it, a) for(it=a.begin(); it!=a.end(); it++)
  63. #define REVSTL(it, a) for(it=a.end(); it!=a.begin(); it--)
  64.  
  65. #define MEM(a,v) memset(a,v,sizeof(a))
  66. #define MAX(x,y) (x)>(y)?(x):(y)
  67. #define MIN(x,y) (x)<(y)?(x):(y)
  68. #define pb push_back
  69. #define pob pop_back
  70. #define b() begin()
  71. #define e() end()
  72. #define s() size()
  73. #define cl() clear()
  74. #define fi first
  75. #define se second
  76. #define INF (1000000000)
  77. #define SZ 100000
  78. #define MOD (1<<30)
  79.  
  80. #define VS vector<string>
  81. #define VI vector<int>
  82. #define VF vector<float>
  83. #define VD vector<double>
  84. #define MII map<int,int>
  85. #define MIS map<int, string>
  86. #define MSI map<string, int> 
  87. #define MSS map<string, string>
  88.  
  89. #define VSI vector<string>::iterator
  90. #define VII vector<int>:iterator
  91. #define VFI vector<float>::iterator
  92. #define VDI vector<double>::iterator
  93. #define MIII map<int,int>::iterator
  94. #define MISI map<int, string>::iterator
  95. #define MSII map<string, int>::iterator 
  96. #define MSSI map<string, string>::iterator
  97. #define print_array(x,n) { for(int i=0; i<n; i++) { cout << x[i] << " " ; } cout << endl; }
  98. #define TEST int T;scanf("%d",&T);while(T--)
  99. #define CASES int N;scanf("%d",&N);while(N--)
  100.  
  101. /* ############################################################################
  102.  * END OF HEADER 
  103.  * ############################################################################
  104. */
  105.  
  106. #define MXN 3001
  107.  
  108. bool visit[MXN];
  109. bool arr[MXN][MXN];
  110. int depth[MXN];
  111. int low_point[MXN];
  112. int high_point[MXN];
  113. int child_count[MXN];
  114. int time_stamp=0;
  115.  
  116. class node {
  117.   public:
  118.     node(int id, int depth, int pid) : node_id_(id), node_depth_(depth), pid_(pid) { }
  119.     ~node() {
  120.       for(int i=0; i<child_.size(); i++) {
  121.         delete child_[i];
  122.       }
  123.     }
  124.     int node_id_;
  125.     int node_depth_;
  126.     int pid_;
  127.     vector<node*> child_;
  128. };
  129.  
  130. node *root_node=NULL;
  131.  
  132. int
  133. calc_low_point(node *cur_node, int N) {
  134.   /* Leaf node */
  135.   if((cur_node->child_).size() == 0) {
  136.     int cur_id          = cur_node->node_id_;
  137.     low_point[cur_id]   = cur_node->node_depth_;
  138.     for(int i=0; i<cur_node->child_.size(); i++) {
  139.       arr[cur_id][cur_node->child_[i]->node_id_] = 0;
  140.     }
  141.     for(int i=0; i<N; i++) {
  142.       if(arr[cur_id][i] && (i != cur_node->pid_)) {
  143.         if(depth[i] < low_point[cur_id]) {
  144.           low_point[cur_id] = depth[i];
  145.         }
  146.       }
  147.     }
  148.     return low_point[cur_id];
  149.   }
  150.   int min_low_point = MXN+1000;
  151.   for(int i=0; i<cur_node->child_.size(); i++) {
  152.     /* Traverse all its childs */
  153.     int x = calc_low_point(cur_node->child_[i], N);
  154.     if(x < min_low_point) {
  155.       min_low_point = x;
  156.     }
  157.   }
  158.   /* Now traverse the cur_node */
  159.   int cur_id          = cur_node->node_id_;
  160.   low_point[cur_id]   = cur_node->node_depth_;
  161.   for(int i=0; i<cur_node->child_.size(); i++) {
  162.     arr[cur_id][cur_node->child_[i]->node_id_] = 0;
  163.   }
  164.   for(int i=0; i<N; i++) {
  165.     if(arr[cur_id][i] && (i != cur_node->pid_)) {
  166.       if(depth[i] < low_point[cur_id]) {
  167.         low_point[cur_id] = depth[i];
  168.       }
  169.     }
  170.   }
  171.   if(min_low_point < low_point[cur_id]) {
  172.     low_point[cur_id] = min_low_point;
  173.   }
  174.   return low_point[cur_id];
  175. }
  176.  
  177. void
  178. dfs_visit(int source, node *parent_node, int N) {
  179.   depth[source]     = ++time_stamp;
  180.   visit[source]     = true;
  181.   node* cur_node;
  182.   if(parent_node == NULL) {
  183.     /* why must this be 0 ?? */
  184.     root_node = new node(source, depth[source], 0);
  185.     cur_node = root_node;
  186.   } else {
  187.     cur_node = new node(source, depth[source], parent_node->node_id_);
  188.     parent_node->child_.pb(cur_node);
  189.   }
  190.   for(int i=0; i<N; i++) {
  191.     if(arr[source][i] && !visit[i]) {
  192.       dfs_visit(i, cur_node, N);
  193.     }
  194.   }
  195. }
  196.  
  197. int
  198. calc_high_point(node *r_node) {
  199.   if(r_node->child_.size() == 0) {
  200.     high_point[r_node->node_id_] = low_point[r_node->node_id_];
  201.     child_count[r_node->node_id_] = 0;
  202.     return high_point[r_node->node_id_];
  203.   }
  204.   int max = -1;
  205.   for(int i=0; i<r_node->child_.size(); i++) {
  206.     int x = calc_high_point(r_node->child_[i]);
  207.     if(x > max) {
  208.       max = x;
  209.     }
  210.   }
  211.   high_point[r_node->node_id_] = max;
  212.   child_count[r_node->node_id_] = r_node->child_.size();
  213.   if(max > low_point[r_node->node_id_]) {
  214.     return max;
  215.   } else {
  216.     return low_point[r_node->node_id_];
  217.   }
  218. }
  219.  
  220. void
  221. pre_order_traversal(node *r_node) {
  222.   cout << r_node->node_id_ << ":" << r_node->node_depth_ << endl;
  223.   for(int i=0; i<r_node->child_.size(); i++) {
  224.     pre_order_traversal(r_node->child_[i]);
  225.   }
  226. }
  227.  
  228. void
  229. post_order_traversal(node *r_node) {
  230.   for(int i=0; i<r_node->child_.size(); i++) {
  231.     post_order_traversal(r_node->child_[i]);
  232.   }
  233.   cout << r_node->node_id_ << ":" << r_node->node_depth_ << endl;
  234. }
  235.  
  236. int find_articulation_points_low(node* root_node, int N) {
  237.   calc_high_point(root_node);
  238. #if DEBUG 
  239.   print_array(high_point, N);
  240.   //cout << "FInal nodes" << endl;
  241. #endif
  242.   int ret=0;
  243.   if(root_node->child_.size() > 1) {
  244.     //cout << 0 << endl;
  245.     ret++;
  246.   }
  247.   for(int i=1; i<N; i++) {
  248.     if((high_point[i] >= depth[i]) && (child_count[i])) {
  249.       //cout << i << endl;
  250.       ret++;
  251.     }
  252.   }
  253.   return ret;
  254. }
  255.  
  256. int 
  257. find_articulation_points(int N) {
  258.   int final = 0;
  259.   /* Reset */
  260.   memset(visit, 0, MXN*sizeof(bool));
  261.   memset(depth, 0, MXN*sizeof(int));
  262.   memset(low_point, 0, MXN*sizeof(int));
  263.   memset(high_point, 0, MXN*sizeof(int));
  264.   memset(child_count, 0, MXN*sizeof(int));
  265.   root_node = NULL;
  266.   /* Do a DFS and get the tree */
  267.   dfs_visit(0, root_node, N);
  268.   /* Do a post order and populate low_point[] */
  269.   calc_low_point(root_node, N);
  270. #if DEBUG
  271.   pre_order_traversal(root_node);
  272.   print_array(depth, N);
  273.   print_array(low_point, N);
  274. #endif
  275.   int ret = find_articulation_points_low(root_node, N);
  276.   /* Clean up */
  277.   delete root_node;
  278.   return ret;
  279. }
  280.  
  281. int main() {
  282. #if DEBUG
  283.   //freopen("in.txt", "r", stdin);
  284. #endif
  285.   TEST {
  286.     int N, M;
  287.     unsigned long long K;
  288.     cin >> N >> M >> K;
  289.     memset(arr, 0, MXN*MXN*sizeof(bool));
  290.     while(M--) {
  291.       int i, j;
  292.       cin >> i >> j;
  293.       arr[i][j] = arr[j][i] = true;
  294.     }
  295.     unsigned long long num_of_pts = find_articulation_points(N); 
  296.     K *= num_of_pts;
  297.     cout << K << endl;
  298.   }
  299. }
Success #stdin #stdout 0s 11888KB
comments (?)
stdin
copy 
1
7 6 5
0 1
1 2
3 4
2 4
2 6
5 2
stdout
copy 
15
https://ideone.com/nhNVCe
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!