正解思路但TLE
查看原帖
正解思路但TLE
977904
Zhong_Yixuan楼主2024/12/21 12:39
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int fa[1003],inv[1003];
set<int> st;
inline ll read(){
	ll ref=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) ref=(ref<<1)+(ref<<3)+ch-48,ch=getchar();
	return ref*f;
}
int find(int i){
	if(fa[i]==0) return i;
	return fa[i]=find(fa[i]);
}
void merge(int a,int b){
	a=find(a),b=find(b);
	if(a!=b) fa[a]=b;
}
int main(){
	int n=read(),m=read();
	while(m--){
		char c;scanf("%c",&c);
		if(c-69){
			merge(read(),read());
		}else{
			int u=read(),v=read();
			if(inv[u]) merge(inv[u],v);
			if(inv[v]) merge(inv[v],u);
			inv[u]=v,inv[v]=u;
		}
	}
	for(int i=1;i<=n;i++) if(inv[i]&&inv[find(i)]) merge(inv[i],inv[find(i)]);
	for(int i=1;i<=n;i++) st.insert(find(i));
	cout<<st.size();

	return 0;
}

无数次的提交显示,66~67 行是 TLE 的罪魁祸首,但这小并查集怎么可能超时

2024/12/21 12:39
加载中...