fork download
copy 
  1. // http://w...content-available-to-author-only...c.jp/k1sakai/Lecture/ALG/2012/ALG2012-B.pdf p.7
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. short currseq;
  6. vector<short> seq;
  7. vector<bool> artic;
  8.  
  9. int dfs(vector<vector<int>>& g, int v)
  10. {
  11.     seq[v]=++currseq;
  12.     int m=currseq;
  13.     for(int u: g[v]) {
  14.         if (!seq[u]) {
  15.             int k=dfs(g, u);
  16.             m=min(m, k);
  17.             bool f=false;
  18.             if (seq[v]==1)
  19.                 f=(seq[u]!=2);
  20.             else
  21.                 f=(k>=seq[v]);
  22.             if (f) artic[v]=true;
  23.         }
  24.         else if (seq[u]<m) {
  25.             m=seq[u];
  26.         }
  27.     }
  28.     return m;
  29. }
  30.  
  31. int main()
  32. {
  33.     ios_base::sync_with_stdio(0);
  34.     cin.tie(0);
  35.  
  36.     int T; cin>>T;
  37.     while (T--) {
  38.         int n, m, k;
  39.         cin>>n>>m>>k;
  40.         vector<vector<int>> g(n);
  41.         seq=vector<short>(n);
  42.         artic=vector<bool>(n);
  43.         currseq=0;
  44.         while (m--) {
  45.             int a, b; cin>>a>>b;
  46.             g[a].push_back(b);
  47.             g[b].push_back(a);
  48.         }
  49.         dfs(g, 0);
  50.         cout<<count(begin(artic), end(artic), true)*k<<endl;
  51.     }
  52. }
  53.  
Runtime error #stdin #stdout #stderr 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/xiZpct
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

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!