-1 
#include <bits/stdc++.h>
using namespace std;

int n;

vector<bool> used;
 vector<int> order, comp;

void dfs1 (int v,const vector<vector<int>>& g) {
used[v] = true;
for (size_t i=0; i<g[v].size(); ++i) {
    int to = g[v][i];
    if (!used[to])
        dfs1 (to,g);
}
order.push_back (v);
}

void dfs2 (int v, int cl,const vector<vector<int>>& gt) {
comp[v] = cl;
for (size_t i=0; i<gt[v].size(); ++i) {
    int to = gt[v][i];
    if (comp[to] == -1)
        dfs2 (to, cl,gt);
}
}

  int main() {
  int q1,q3;
  cin>>q1>>n>>q3;

  n*=2;
  vector < vector<int> > g(n), gt(n);
  vector< vector< int> > adj(q1+5);
    int o,oo;
  for(int i=0;i<q3;i++){
         cin>>o>>oo;
         if(oo<0){
           oo+=1;
           adj[o].push_back((oo*-1)*2+1);   
         } else{

           oo-=1;
              adj[o].push_back(oo*2);

         }

  }   

  for(int i=1;i<=q1;i++){

       for(int j=0;j<adj[i].size();j++){
            for(int k=0;k<adj[i].size();k++){

                    if(j!=k){
                   g[adj[i][j]^1].push_back(adj[i][k]);
                        gt[adj[i][k]].push_back(adj[i][j]^1);
                       }
              } }
              }  



     used.assign (n+1, false);
 for (int i=0; i<n; ++i)
    if (!used[i])
        dfs1 (i,g);

comp.assign (n+1, -1);
for (int i=0, j=0; i<n; ++i) {
    int v = order[n-i-1];
    if (comp[v] == -1)
        dfs2 (v, j++,gt);
}

for (int i=0; i<n; ++i)
    if (comp[i] == comp[i^1]) {
 cout<<-1;
        return 0;
    }
vector<int> answ;

for (int i=0; i<n; i+=2) {
    int ans = comp[i] > comp[i^1] ? i : i^1;
      if(ans%2==0){
        ans/=2;

        ans++;
              answ.push_back(ans);

  }
}
cout<<answ.size()<<endl;
for(int i=0;i<answ.size();i++){
cout<<answ[i]<<endl;
}



 }

这是解决与 2SAT 相关的问题的代码。当输入值 n=200 000 时，此代码超出了 512 mB 的内存限制。我可以使用哪些技巧来减少内存使用？我已经尝试在主代码中分配向量 g 和 gt，然后在 dfs 和 dfs2 函数中我放置 g 和 gt 但这给了我时间限制问题。我如何优化这段代码？

4

1 回答 1

0

您没有同时使用 g 和 gt。所以清除g并在那之后保留gt。（comp.assign (n+1, -1);在此行之前）

与 used 和 comp 相同。

used并且adj不会同时使用。adj行前清除used.assign (n+1, false);

尝试将adj其用作 C 风格的 vector( int**) 和另一个用于各个尺寸的向量。

于 2018-11-18T09:40:39.730 回答