Submission #603354

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
603354	2022-07-24T04:30:43 Z	조영욱(#8429)	Collapse (JOI18_collapse)	C++17	Compilation error	0 ms	0 KB

collapse

//����: tarjan ���� ȣ��

vector<int> G[MAX_V];
int In[MAX_V], Low[MAX_V], P[MAX_V];
void addEdge(int s, int e){
  G[s].push_back(e); G[e].push_back(s);
}
void tarjan(int n){ /// Pre-Process
  int pv = 0;
  function<void(int,int)> dfs = [&pv,&dfs](int v, int b){
    In[v] = Low[v] = ++pv; P[v] = b;
    for(auto i : G[v]){
      if(i == b) continue;
      if(!In[i]) dfs(i, v), Low[v] = min(Low[v], Low[i]);
      else Low[v] = min(Low[v], In[i]);
    }
  };
  for(int i=1; i<=n; i++) if(!In[i]) dfs(i, -1);
}
vector<int> cutVertex(int n){
  vector<int> res;
  array<char,MAX_V> isCut; isCut.fill(0);
  function<void(int)> dfs = [&dfs,&isCut](int v){
    int ch = 0;
    for(auto i : G[v]){
      if(P[i] != v) continue; dfs(i); ch++;
      if(P[v] == -1 && ch > 1) isCut[v] = 1;
      else if(P[v] != -1 && Low[i] >= In[v]) isCut[v] = 1;
    }
  };
  for(int i=1; i<=n; i++) if(P[i] == -1) dfs(i);
  for(int i=1; i<=n; i++) if(isCut[i]) res.push_back(i);
  return move(res);
}
vector<PII> cutEdge(int n){
  vector<PII> res;
  function<void(int)> dfs = [&dfs,&res](int v){
    for(int t=0; t<G[v].size(); t++){
      int i = G[v][t]; if(t != 0 && G[v][t-1] == G[v][t]) continue;
      if(P[i] != v) continue; dfs(i);
      if((t+1 == G[v].size() || i != G[v][t+1]) && Low[i] > In[v]) res.emplace_back(min(v,i), max(v,i));
    }
  };
  for(int i=1; i<=n; i++) sort(G[i].begin(), G[i].end()); // multi edge -> sort
  for(int i=1; i<=n; i++) if(P[i] == -1) dfs(i);
  return move(res); // sort(all(res));
}
vector<int> BCC[MAX_V]; // BCC[v] = components which contains v
void vertexDisjointBCC(int n){ // allow multi edge, not allow self loop
  int cnt = 0;
  array<char,MAX_V> vis; vis.fill(0);
  function<void(int,int)> dfs = [&dfs,&vis,&cnt](int v, int c){
    if(c > 0) BCC[v].push_back(c);
    vis[v] = 1;
    for(auto i : G[v]){
      if(vis[i]) continue;
      if(In[v] <= Low[i]) BCC[v].push_back(++cnt), dfs(i, cnt);
      else dfs(i, c);
    }
  };
  for(int i=1; i<=n; i++) if(!vis[i]) dfs(i, 0);
  for(int i=1; i<=n; i++) if(BCC[i].empty()) BCC[i].push_back(++cnt);
}
void edgeDisjointBCC(int n){} // remove cut edge, do flood fill

Compilation message

collapse.cpp:3:1: error: 'vector' does not name a type
    3 | vector<int> G[MAX_V];
      | ^~~~~~
collapse.cpp:4:8: error: 'MAX_V' was not declared in this scope
    4 | int In[MAX_V], Low[MAX_V], P[MAX_V];
      |        ^~~~~
collapse.cpp:4:20: error: 'MAX_V' was not declared in this scope
    4 | int In[MAX_V], Low[MAX_V], P[MAX_V];
      |                    ^~~~~
collapse.cpp:4:30: error: 'MAX_V' was not declared in this scope
    4 | int In[MAX_V], Low[MAX_V], P[MAX_V];
      |                              ^~~~~
collapse.cpp: In function 'void addEdge(int, int)':
collapse.cpp:6:3: error: 'G' was not declared in this scope
    6 |   G[s].push_back(e); G[e].push_back(s);
      |   ^
collapse.cpp: In function 'void tarjan(int)':
collapse.cpp:10:3: error: 'function' was not declared in this scope; did you mean 'union'?
   10 |   function<void(int,int)> dfs = [&pv,&dfs](int v, int b){
      |   ^~~~~~~~
      |   union
collapse.cpp:10:24: error: expression list treated as compound expression in functional cast [-fpermissive]
   10 |   function<void(int,int)> dfs = [&pv,&dfs](int v, int b){
      |                        ^
collapse.cpp:10:12: error: expected primary-expression before 'void'
   10 |   function<void(int,int)> dfs = [&pv,&dfs](int v, int b){
      |            ^~~~
collapse.cpp:18:31: error: 'In' was not declared in this scope; did you mean 'n'?
   18 |   for(int i=1; i<=n; i++) if(!In[i]) dfs(i, -1);
      |                               ^~
      |                               n
collapse.cpp:18:38: error: 'dfs' was not declared in this scope
   18 |   for(int i=1; i<=n; i++) if(!In[i]) dfs(i, -1);
      |                                      ^~~
collapse.cpp:9:7: warning: unused variable 'pv' [-Wunused-variable]
    9 |   int pv = 0;
      |       ^~
collapse.cpp: At global scope:
collapse.cpp:20:1: error: 'vector' does not name a type
   20 | vector<int> cutVertex(int n){
      | ^~~~~~
collapse.cpp:35:1: error: 'vector' does not name a type
   35 | vector<PII> cutEdge(int n){
      | ^~~~~~
collapse.cpp:48:1: error: 'vector' does not name a type
   48 | vector<int> BCC[MAX_V]; // BCC[v] = components which contains v
      | ^~~~~~
collapse.cpp: In function 'void vertexDisjointBCC(int)':
collapse.cpp:51:3: error: 'array' was not declared in this scope
   51 |   array<char,MAX_V> vis; vis.fill(0);
      |   ^~~~~
collapse.cpp:51:9: error: expected primary-expression before 'char'
   51 |   array<char,MAX_V> vis; vis.fill(0);
      |         ^~~~
collapse.cpp:51:26: error: 'vis' was not declared in this scope
   51 |   array<char,MAX_V> vis; vis.fill(0);
      |                          ^~~
collapse.cpp:52:3: error: 'function' was not declared in this scope; did you mean 'union'?
   52 |   function<void(int,int)> dfs = [&dfs,&vis,&cnt](int v, int c){
      |   ^~~~~~~~
      |   union
collapse.cpp:52:24: error: expression list treated as compound expression in functional cast [-fpermissive]
   52 |   function<void(int,int)> dfs = [&dfs,&vis,&cnt](int v, int c){
      |                        ^
collapse.cpp:52:12: error: expected primary-expression before 'void'
   52 |   function<void(int,int)> dfs = [&dfs,&vis,&cnt](int v, int c){
      |            ^~~~
collapse.cpp:61:39: error: 'dfs' was not declared in this scope
   61 |   for(int i=1; i<=n; i++) if(!vis[i]) dfs(i, 0);
      |                                       ^~~
collapse.cpp:62:30: error: 'BCC' was not declared in this scope
   62 |   for(int i=1; i<=n; i++) if(BCC[i].empty()) BCC[i].push_back(++cnt);
      |                              ^~~