CF231E莫名奇妙TLE#4

Question

莫名奇妙TLE#4

传送门

#include<bits/stdc++.h>
  


using namespace std;

const int MAXX = 3e5 + 5;

const int MOD = 1e9 + 7;

int n, m, vis[MAXX], dcc[MAXX], dfn[MAXX], low[MAXX], cnt, num, u[MAXX], v[MAXX], flag[MAXX], sum, ans, q, x, y, deep[MAXX], dis[MAXX], f[MAXX][20];
vector<pair<int, int> > e[MAXX];
vector<int> G[MAXX];

void tarjan(int x, int fa){
    dfn[x] = low[x] = ++cnt;
    for(int i = 0; i < e[x].size(); i++){
        int y = e[x][i].first;
        int id = e[x][i].second;
        if(!dfn[y]){
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if(dfn[x] < low[y]){
                vis[id] = 1;
            }
        }else if(y != fa){
            low[x] = min(low[x], dfn[y]);
        } 
    }
}

void dfs(int x){
  sum++;
    dcc[x] = num;
    for(int i = 0; i < e[x].size(); i++){
        int y = e[x][i].first;
        int id = e[x][i].second;
        if(!dcc[y] && !vis[id]){
            dfs(y);
        }
    }
}

int Dfs(int x, int fa){
    for(int i = 1; i <= 16; i++){
        if(deep[x] < (1 << i)) break;
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for(int i = 0; i < G[x].size(); i++){
      int y = G[x][i];
        if(y == fa) continue;
        deep[y] = deep[x] + 1;
        dis[y] = dis[x] + (flag[x] == 2);
        f[y][0] = x;
        Dfs(y, x);  
    }
}

int lca(int x, int y){
    if(deep[x] < deep[y]){
        swap(x, y);
    }
    int d = deep[x] - deep[y];
    for(int i = 0; i <= 16; i++){
        if((1 << i) & d)
            x = f[x][i];
    }
    if(x == y){
        return x;
    }
    for(int i = 16; i >= 0; i++){
        if(f[x][i] != f[y][i]){
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}

int pow(int b,int p){
   int ret = 1;
   while(p){
     if(p % 2) ret = ret * b % MOD;
     b = b * b % MOD;
     p /= 2;
   }
   return ret;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> u[i] >> v[i];
        e[u[i]].push_back({v[i], i});
        e[v[i]].push_back({u[i], i});
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]){
            tarjan(i, -1);
        }
    }
    for(int i = 1; i <= n; i++){
        if(!dcc[i]){
            num++;
            sum = 0;
            dfs(i); 
            if(sum == 1){
              flag[num] = 1;
      }else{
        flag[num] = 2;
      }
        }
    }
    for(int i = 1; i <= m; i++){
      if(dcc[u[i]] != dcc[v[i]]){
        G[dcc[u[i]]].push_back(dcc[v[i]]);
        G[dcc[v[i]]].push_back(dcc[u[i]]);
    }
  }
  dis[1] = (flag[1] == 2);
  Dfs(1, -1);
    cin >> q;
    while(q--){
      cin >> x >> y;
      x = dcc[x], y = dcc[y];
      if(x == y){
        cout << flag[x] << '\n';
        continue;
    }
      int fa = lca(x, y);
      cout << pow(2, dis[x] + dis[y] - 2 * dis[fa]) << '\n';
  }
    
    return 0;
}

Answer 1

本答案参考多次询问ChatGPT-3.5后选择的最佳回答，若是满意，还请采纳，谢谢。

你的代码在处理TLE（Time Limit Exceeded，时间超限）问题时，可能存在几个效率问题。以下是一些可能的原因和解决方案：

1. 深度优先搜索（DFS）和Tarjan算法的效率：

   • Tarjan算法用于寻找强连通分量，但你的实现可能不是最优的。确保每个节点只被访问一次，并且递归调用尽可能少。

2. 二叉提升（Binary Lifting）的实现：

   • 你的Dfs函数和lca函数实现的二叉提升算法可能不够高效。确保你的Dfs函数只计算必要的祖先，并在lca函数中正确使用二进制提升。

3. 幂运算的优化：

   • 你的pow函数每次调用都会从头计算幂，这在大量查询时会导致不必要的重复计算。可以考虑使用记忆化或迭代方法来优化。

4. 图的构建：

   • 在构建图G时，你使用了两个循环来添加边。这可能导致不必要的重复工作。确保每个边只被添加一次。

5. 查询处理：

   • 在处理查询时，你每次都计算LCA和距离，这可能导致时间复杂度过高。考虑预先计算并存储一些信息，以减少查询时的计算量。

以下是一些代码优化建议：

优化Tarjan算法

确保每个节点只被访问一次：

void tarjan(int x, int fa) {
    dfn[x] = low[x] = ++cnt;
    vis[x] = 1;  // 标记为已访问
    for (int i = 0; i < e[x].size(); i++) {
        int y = e[x][i].first;
        int id = e[x][i].second;
        if (!dfn[y]) {
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if (dfn[x] < low[y]) {
                vis[id] = 1;
            }
        } else if (y != fa && vis[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
}

优化二叉提升

确保Dfs函数只计算必要的祖先：

int Dfs(int x, int fa) {
    for (int i = 1; i <= 16; i++) {
        if (deep[x] < (1 << i)) break;
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int i = 0; i < G[x].size(); i++) {
        int y = G[x][i];
        if (y == fa) continue;
        deep[y] = deep[x] + 1;
        dis[y] = dis[x] + (flag[x] == 2);
        f[y][0] = x;
        Dfs(y, x);
    }
    return 0;
}

优化幂运算

使用迭代方法来优化幂运算：

int pow(int b, int p) {
    int ret = 1;
    while (p) {
        if (p & 1) ret = ret * b % MOD;
        b = b * b % MOD;
        p >>= 1;
    }
    return ret;
}

优化图的构建

确保每个边只被添加一次：

for (int i = 1; i <= m; i++) {
    if (dcc[u[i]] != dcc[v[i]]) {
        G[dcc[u[i]]].push_back(dcc[v[i]]);
        G[dcc[v[i]]].push_back(dcc[u[i]]);
    }
}

通过这些优化，你的代码应该能够更有效地处理大量数据和查询，减少TLE问题。如果问题仍然存在，请进一步检查数据输入和算法逻辑。