小w來到百度之星的賽場上，準(zhǔn)備開始實現(xiàn)一個程序自動分析系統(tǒng)。
這個程序接受一些形如xi=xj 或 xi≠xj
的相等/不等約束條件作為輸入，判定是否可以通過給每個 w 賦適當(dāng)?shù)闹?#xff0c;來滿足這些條件。

輸入包含多組數(shù)據(jù)。
然而粗心的小w不幸地把每組數(shù)據(jù)之間的分隔符刪掉了。
他只知道每組數(shù)據(jù)都是不可滿足的，且若把每組數(shù)據(jù)的最后一個約束條件去掉，則該組數(shù)據(jù)是可滿足的。
請幫助他恢復(fù)這些分隔符。
Input
第1行：一個數(shù)字L，表示后面輸入的總行數(shù)。
之后L行，每行包含三個整數(shù)，i,j,e，描述一個相等/不等的約束條件，若e=1，則該約束條件為xi=xj ，若e=0，則該約束條件為 xi≠xj 。
i,j,L≤100000 xi,xj≤L
Output
輸出共T+1行。
第一行一個整數(shù)T，表示數(shù)據(jù)組數(shù)。
接下來T行的第i
行，一個整數(shù)，表示第i組數(shù)據(jù)中的約束條件個數(shù)。
Sample Input
6
2 2 1
2 2 1
1 1 1
3 1 1
1 3 1
1 3 0
Sample Output
1
6

看起來就是一個并查集。可是對于不相等的關(guān)系，我們只能暴力保存。剛開始我用了一個數(shù)組表保存，相等關(guān)系的時候都查詢一次有沒有和之前的不等關(guān)系沖突。成功超時。

看題解了解到要用set，的確用set的話查找操作更加方便，空間復(fù)雜度也更好。

對每個節(jié)點都建立一個set，用于保存不能和他們相等的元素。隨著相等元素的增多，我們也得同時合并他們的不等元素。將這些元素都保存在并查集的根節(jié)點處，合并的時候根據(jù)這個set的大小進行合并，盡量是小的合并到大的里面。注意在將set中的元素插入到另一個set中時，需要將該元素所指向元素中的set的值全部修改（相當(dāng)于修改他們的代表，換老大了）

再建立一個set用于記錄出現(xiàn)過的節(jié)點，這樣就不用memset恢復(fù)并查集數(shù)組了。

#include<iostream> #include<cstring> #include<cstdio> #include<climits> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> #include<set> #include<map> #include<cmath>using namespace std;const int MAXN=1e5+5; int Equal[MAXN]; int L,T,len; set<int> un[MAXN],st; int tot=0; int ans[MAXN];int find(int x) {if(Equal[x]==0){Equal[x]=x; return x;}if(x==Equal[x]) return x;int t=x;while(t!=Equal[t]) t=Equal[t];int y=x,z;while(Equal[y]!=t){z=Equal[y]; Equal[y]=t; y=z;}return t; }void Union(int x,int y) {if(un[x].size()>un[y].size()) swap(x,y);set<int>::iterator it;for(it=un[x].begin();it!=un[x].end();it++){un[*it].erase(x);un[*it].insert(y);un[y].insert(*it);}Equal[x]=y; }int main() {T=0; len=0;int u,v,w;bool wrong=false;scanf("%d",&L);set<int>::iterator it;while(L--){len++;scanf("%d%d%d",&u,&v,&w);st.insert(u); st.insert(v);int rt1=find(u),rt2=find(v);if(w==1){if(rt1==rt2){continue;}else{if(un[rt1].count(rt2)==0){Union(rt1,rt2);}else{wrong=true;}}}else{if(rt1==rt2){wrong=true;}else{un[rt1].insert(rt2);un[rt2].insert(rt1);}}if(wrong){for(it=st.begin();it!=st.end();it++){Equal[*it]=*it;un[*it].clear();}st.clear();ans[++T]=len;len=0;tot=0;wrong=false;}}printf("%d\n",T);for(int i=1;i<=T;i++){printf("%d\n",ans[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的数据分割-并查集+set的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。