36pts 求大佬帮调
查看原帖
36pts 求大佬帮调
355559
FutureThx楼主2020/9/18 13:19

tarjan写挂了,TLE 先不管,但就是WA

#include <iostream>
using namespace std;
struct node{
    int u,v;
}edge[100001];
int num[100001],low[100001],n,m,root,t = 0;
int index = 0;
int flag[100001];
inline int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
void tarjan(int cur,int father){
    int child = 0;
    index++;
    num[cur] = index;
    low[cur] = index;
    for(int i = 1;i <= m;i++){
        if(edge[i].u == cur || edge[i].v == cur){
            int x = edge[i].u == cur ? edge[i].v : edge[i].u;
            if(num[x] == 0){
                child++;
                tarjan(x,cur);
                low[cur] = min(low[x],low[cur]);
                if(cur != root && low[x] >= num[cur])flag[cur] = 1;
                if(cur == root && child == 2)flag[cur] = 1;
            }
            else
               if(x != father)
                  low[cur] = min(num[x],low[cur]);
        }
    }
    return;
}
int main(){
    n = read();
    m = read();
    for(int i = 1;i <= m;i++){
        edge[i].u = read();
        edge[i].v = read();
    }
    root = 1;
    tarjan(1,root);
    for(int i = 1;i <= n;i++)
        if(flag[i] == 1)
           t++;
    cout << t << endl;
    for(int i = 1;i <= n;i++)
        if(flag[i] == 1)
           cout << i << " ";
    return 0;
}

怎么改啊,求助大佬指点

2020/9/18 13:19
加载中...