有关MLE的问题
  • 板块学术版
  • 楼主StrFaith
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/17 10:45
  • 上次更新2023/11/17 14:07:08
查看原帖
有关MLE的问题
970752
StrFaith楼主2023/11/17 10:45

求割点模板代码:

1. #include <bits/stdc++.h>
using namespace std;
int n, m;
const int maxn = 1e5+1;
struct edge{
    int v, nxt;
}edge[maxn <<1];
int head[maxn];
int cnt = 0;
void addedge(int u, int v) {
    cnt++;
    edge[cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
int low[maxn], num[maxn], dfn = 0;
int iscut[maxn];
void dfs(int u, int fa) {
    low[u] = num[u] = ++dfn;
    int child = 0;
    for(int i =head[u]; i ; i = edge[i].nxt) {
        int v = edge[i].v;
        if(!num[v]) {
            if(u == fa) child++;
            dfs(v, u);
            low[u] = min(low[v], low[u]);
            if(low[v] >= num[u] && u != fa) {
                iscut[u] =1;
            }

        }
        else if(num[v] < num[u] && v != fa)
            low[u] = min(low[u], num[v]);
    }
    if( u == fa && child >= 2) {
        iscut[fa] = 1;
    }
}
int main() {
    cin >> n >> m;
    for(int i = 1; i<= m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        addedge(a, b);
        addedge(b, a);
    }
    for(int i =1; i<= n ;i++){
        if(!num[i]) dfs(i, i);
    }
    int ans = 0;
    for(int i =1; i<= n; i++)
        ans += iscut[i];
    printf("%d\n", ans);
    for(int i =1; i<= n; i++)
        if(iscut[i]) printf("%d ", i);
    return 0;
}

为什么 把!num[v]改成v != fa会爆栈阿?

2023/11/17 10:45
加载中...