时间复杂度正确,为什么TLE(qwq)
查看原帖
时间复杂度正确,为什么TLE(qwq)
1632009
pxn1234楼主2025/7/25 18:16

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int N = 3e6 + 10;
const int Mod = 998244353;

int n,m;
struct vecEdge {
    int y,v;
};
vector<vecEdge>G[N];
int dfn[N],low[N],dfc;
int InStack[N];
stack<int>stk;
int color[N],tot;
int val[N];

void tarjan(int x,int pre) {
    dfn[x]=low[x]=++dfc;
    InStack[x]=true;
    stk.push(x);
    for(vecEdge i:G[x]) {
        int y=i.y;
        if(y==pre) continue;
        if(!dfn[y]) {
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
        } else if(InStack[y]) {
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x]) {
        tot++;
        while(stk.top()!=x) {
            color[stk.top()]=tot;
            InStack[stk.top()]=false;
            stk.pop();
        }
        color[x]=tot;
        InStack[x]=false;
        stk.pop();
    }
}

vector<vecEdge>tr[N];
map<pii,int>mp;
int a,b;

void dfs(int x,int pre,bool flag) {
    if(val[x]) flag=true;
	if(x==color[b]&&flag) printf("YES"),exit(0);
    for(vecEdge i:tr[x]) {
        int y=i.y;
        if(y==pre) continue;
        dfs(y,x,flag|i.v);
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        G[x].push_back({y,v});
        G[y].push_back({x,v});
    }
    for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i,0);
    for(int x=1; x<=n; x++) {
        for(vecEdge i:G[x]) {
            int y=i.y;
            if(color[x]!=color[y]) {
                if(mp[ {color[x],color[y]}]) continue;
                mp[ {color[x],color[y]}]=1;
                tr[color[x]].push_back({color[y],i.v});
                tr[color[y]].push_back({color[x],i.v});
            } else if(i.v==1) val[color[x]]=1;
        }
    }
    scanf("%d%d",&a,&b);
    dfs(color[a],0,0);
    printf("NO");
    return 0;
}

2025/7/25 18:16
加载中...