90分WA#7求调!

P1892 [BOI2003] 团伙

`if(a == 'E'){}`中要双向建边 另外`e[i] = j`要改成`e[i] = get[j]`否则会MLE(?)
by Hatsune_Miku_ @ 2023-11-24 22:12:06


@[Hatsune_Miku_](/user/544500) 啊那具体该怎么做嘞(蒟蒻不解)
by yzysdTNT @ 2023-11-24 22:17:36


```cpp if(a == 'F') p[get(x)] = get(y); else{ if(e[x] == 0) e[x] = get(y); else p[get(y)] = get(e[x]); if(e[y] == 0) e[y] = get(x); else p[get(x)] = get(e[y]); } ```
by Hatsune_Miku_ @ 2023-11-24 22:23:18


@[Hatsune_Miku_](/user/544500) 过了,谢谢大佬,已关 %%% orz
by yzysdTNT @ 2023-12-02 10:31:08


@[Hatsune_Miku_](/user/544500) 大佬求调wr #7 ```cpp // Problem: // P1892 [BOI2003] 团伙 // // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P1892 // Memory Limit: 125 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<algorithm> //#include<cstdio> #include<map> #include<set> #define ll long long #define endl '\n' #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>(b);i--) #define N 1010//1e6+100 #define M 5010 using namespace std; int n,m; int f[N],p,q; char opt; int cnt=0; set<int>s[M]; void Init(){ rep(i,1,n){ f[i]=i; } } //朋友的朋友可以直接用并查集板子 //敌人的敌人怎么变成朋友呢? //1.敌人的敌人的敌人的敌人是朋友 //2.敌人的敌人的敌人是敌人 //3.敌人的敌人的朋友是朋友 int find(int x){ if(x==f[x]) return x; else return f[x]=find(f[x]); } void merge(int i,int j){ f[find(i)]=f[find(j)]; } int main(){ //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>m; Init(); rep(i,1,m){ cin>>opt>>p>>q; if(opt=='F') merge(p,q); else if(opt=='E'){ s[p].insert(q); s[q].insert(p); } } int res; rep(i,1,n){ if(s[i].size()<=1) continue; for(auto item:s[i]){ if(f[item]!=item){ res=item; break; } } for(auto item:s[i]){ if(find(item)!=find(i)) f[item]=f[res]; } } int cnt=0; // rep(i,1,n){ // cout<<f[i]<<" "; // }cout<<endl; rep(i,1,n){ if(f[i]==i) cnt++; } cout<<cnt<<endl; return 0; } ```
by lightme @ 2024-03-21 16:47:31


|