題目分析

• 該代碼實現了一個動態集合管理系統，支持三種操作：合并集合、切換元素狀態、查詢集合中是否- 存在活躍元素。核心數據結構為并查集，結合狀態標記數組和計數器。
• 關鍵數據結構與函數

初始化

• fa[N]：并查集父節點數組，初始時每個元素自成一集合。
• cnt[N]：記錄每個集合中活躍元素的數量。
• f[N]：標記元素是否活躍（true表示活躍）。
• 路徑壓縮：查找時直接指向根節點，優化后續查詢效率。
• 按大小合并：將較小集合的根指向較大集合的根，并累加活躍元素計數。
• 動態更新元素活躍狀態，并同步調整所屬集合的計數器。

操作處理流程

• 合并集合（op=1）
• 輸入兩個元素u和v，合并其所屬集合。
• 切換狀態（op=2）
• 輸入元素u，反轉其活躍狀態并更新集合計數器。
• 查詢集合（op=3）
• 輸入元素u，檢查其所屬集合是否存在活躍元素（cnt[find(u)] > 0）。

復雜度分析

• 時間復雜度：單次find操作接近$O(\alpha (n))$（反阿克曼函數），整體操作復雜度為$O(q?\alpha (n))$。
• 空間復雜度：$O(n)$，用于存儲父節點、計數器和狀態數組。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,fa[N],cnt[N];
bool f[N];
int find(int x)
{return (x==fa[x]?x:fa[x]=find(fa[x]));
}
void merge(int x,int y)
{x=find(x),y=find(y);if(x!=y) fa[x]=y,cnt[y]+=cnt[x];
}
void change(int x)
{int fx=find(x);if(f[x]) cnt[fx]--;else cnt[fx]++;f[x]=!f[x];
}
signed main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=1;i<=n;i++) fa[i]=i;int op,u,v;while(q--){cin>>op;if(op==1){cin>>u>>v;merge(u,v);}else if(op==2){cin>>u;change(u);}else{cin>>u;if(cnt[find(u)]) cout<<"Yes"<<'\n';else cout<<"No"<<'\n';}}return 0;
}