你告诉我线性时间复杂度会T是吧
查看原帖
你告诉我线性时间复杂度会T是吧
999274
CNS_5t0_0r2楼主2023/11/17 12:53
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9,M = 3e5 + 9;
int read() {
	char c = getchar();
	int x = 0;
	while (c < '0' || c > '9')
		c = getchar();
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x;
}
struct graph{
	struct edge{
		int to,cost,nex;
	} e[M << 1];
	int head[N],ecnt;
	void addedge(int u,int v,int w){
		ecnt++;
		e[ecnt] = (edge){v,w,head[u]};
		head[u] = ecnt;
	}
} G;
int id,dfn[N],low[N];
bool check[M << 1],vis[N],check2[N];//check[i]:边i是否为割边;vis[i]:点i是否被访问(dfs2);check2[i]边双连通分量i中是否存在有疏导的边 
int dcc[N],in[N],cnt;//dcc[i]表示第i个边双连通分量中有多少个点 ,in[i]表示i在第几个边双连通分量中
int fa[N];
int father(int x){
	return fa[x] == x ? x : father(fa[x]);
}
void join(int x,int y){
	int fa_x = father(x),fa_y = father(y);
	fa[fa_x] = fa_y;
}
int ans[N],ans2[N];
int backward(int i){
	return i & 1 ? i + 1 : i - 1;
}
void dfs(int u,int fa){
	id++;
	dfn[u] = low[u] = id;
	for(int i = G.head[u];i;i = G.e[i].nex){
		int v = G.e[i].to;
		if(v != fa){
			if(!dfn[v]){
				dfs(v,u);
				if(low[v] > dfn[u])
					check[i] = check[backward(i)] = true;
				low[u] = min(low[u],low[v]);
			}
			else
				low[u] = min(low[u],dfn[v]);
		}
	}
}
void dfs2(int u, int dcc_id){
    vis[u] = true;
    in[u] = dcc_id;
    dcc[dcc_id]++;
    for (int i = G.head[u];i;i = G.e[i].nex){
        int v = G.e[i].to;
        if (vis[v] || check[i])
            continue;
        if(G.e[i].cost)
        	check2[dcc_id] = true;
        dfs2(v, dcc_id);
    }
}
int n,m;
int main(){
	n = read();m = read();
	for(int i = 1;i <= m;i++){
		int u = read(),v = read(),w = read();
		G.addedge(u,v,w);
		G.addedge(v,u,w);
	}
	dfs(1,0);
	for(int i = 1;i <= n;i++)
		if(!vis[i]){
			dfs2(i,++cnt);
		}
	for(int i = 1;i <= cnt;i++)
		fa[i] = i;
	for(int i = 1;i <= G.ecnt;i += 2){
		int u = G.e[i].to,v = G.e[backward(i)].to,w = G.e[i].cost;
        if((in[u] != in[v]) && (!check2[in[u]] && !check2[in[v]]) && !w)
        	join(in[u],in[v]);
	}
	int a = read(),b = read();
	int in_a = in[a],in_b = in[b];
	if(in_a == in_b)
		puts(check2[in_a] ? "YES" : "NO");
	else
		puts(father(in[a]) == father(in[b]) ? "NO" : "YES");
	return 0;
}
2023/11/17 12:53
加载中...