# 寒假集训第一天—并查集题解（更毕

0
16

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10 ;
int fa[maxn], cnt[maxn], vis[maxn], arr[maxn] ;
int fi(int x)
{
return x == fa[x] ? x : fa[x] = fi(fa[x]) ;
}
int main(int argc, char const *argv[])
{
int n , m ;
scanf("%d %d",&n,&m) ;
for(int i = 1 ; i <= n ; ++ i) fa[i] = i, cnt[i] = 0, vis[i] = 0, arr[i] = 0 ;
for(int i = 1, a, b ; i <= m ; ++ i)
{
scanf("%d %d",&a,&b) ;
cnt[a] ++ ;
cnt[b] ++ ;
vis[a] = 1 ;
vis[b] = 1 ;
int fx = fi(a), fy = fi(b) ;
if(fx != fy) fa[fx] = fy ;
}
int ans = 0 , tot = 0 ;
for(int i = 1 ; i <= n ; ++ i)
{
if(cnt[i] % 2 == 1)
{
arr[fi(i)] ++ ;
}
}
int ff = 0 ;
int cnt2 = 0 , cnt1 = 0;
for(int i = 2 ; i <= n ; ++ i) if(vis[i] == 1) ff = 1 ;
int cnt = 0 ;
for(int i = 1 ; i <= n ; ++ i)
{
if(vis[i] && fa[i] == i && arr[i] >= 2)//有奇度顶点的连通块
{
tot = tot + (arr[i] - 2) / 2 ;
++ cnt2 ;//奇度顶点数
}
if(vis[i] && fa[i] == i) tot += 1, cnt ++ ;//顶点数
}
cnt1 = cnt - cnt2 ;
//printf("%d %d %d\n",cnt1,cnt2,cnt) ;
if(cnt == 1)
{
if(cnt1 == 1)
{
if(vis[1] == 0) printf("2\n") ;
else printf("0\n") ;
}
else if(cnt2 == 1)
{
if(vis[1] == 0) tot ++ ;
printf("%d\n",tot) ;
}
}
else if(cnt == 0)
{
printf("0\n") ;
}
else if(cnt >= 2)
{
if(vis[1] == 0) ++ tot ;
printf("%d\n",tot) ;
}
return 0;
}```

View Code

CodeForces – 468BTwo Sets

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10 ;
int fa[maxn], arr[maxn], brr[maxn] ;
set<int> se ;
map<int,int> mp ;
int fd(int x)
{
return x == fa[x] ? fa[x] : fa[x] = fd(fa[x]) ;
}
void un(int x , int y)
{
int xx = fd(x) ;
int yy = fd(y) ;
if(xx != yy) fa[yy] = xx ;
}
int main(int argc, char const *argv[])
{
int n, a, b ;
se.clear() ;
mp.clear() ;
scanf("%d %d %d",&n,&a,&b) ;
memset(brr,-1,sizeof brr) ;
for(int i = 1 ; i <= n ; ++ i)
{
scanf("%d",&arr[i]) ;
fa[i] = i ;
se.insert(arr[i]) ;
mp[arr[i]] = i ;
}
fa[n+1] = n+1 ; fa[n+2] = n+2 ;
for(int i = 1 ; i <= n  ; ++ i)
{
if(se.count(a-arr[i])) un(i,mp[a-arr[i]]) ;
else un(i,n+1) ;

if(se.count(b-arr[i])) un(i,mp[b-arr[i]]) ;
else un(i,n+2) ;
}
if(fd(n+1) == fd(n+2))
{
printf("NO\n") ;
return 0 ;
}
printf("YES\n") ;
for(int i = 1 ; i <= n ; ++ i)
{
printf("%d%c",(fd(i) == fd(n+1) ? 1 : 0)," \n"[i == n]) ;
}
return 0;
}```

View Code

CodeForces – 722CDestroying Array

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10 ;
#define ll long long
ll arr[maxn], val[maxn], val2[maxn] ;
int brr[maxn], fa[maxn], vis[maxn] ;
int fi(int x)
{
return x == fa[x] ? fa[x] : fa[x] = fi(fa[x]) ;
}
int main(int argc, char const *argv[])
{
int n ;
scanf("%d",&n) ;
memset(val,0,sizeof val) ;
memset(vis,0,sizeof vis) ;
memset(val2,0,sizeof val2) ;
for(int i = 1 ; i <= n ; ++ i) scanf("%lld",&arr[i]), fa[i] = i ;
for(int i = 1 ; i <= n ; ++ i) scanf("%d",&brr[n-i+1]) ;
ll MAX = 0 ;
for(int i = 1 ; i <= n ; ++ i)
{
val2[i] = MAX ;
int pos = brr[i] ;
vis[pos] = 1 ;
int xx = fi(pos) ;
int yy ;
if(pos != 1)
{
if(vis[pos-1])
{
yy = fi(pos-1) ;
val[pos] += val[yy] ;
if(xx != yy) fa[yy] = xx ;
}
}
if(pos != n)
{
if(vis[pos+1])
{
yy = fi(pos+1) ;
val[pos] += val[fi(pos+1)] ;
if(xx != yy) fa[yy] = xx ;
}
}
val[pos] += arr[pos] ;
MAX = max(MAX,val[pos]) ;
}
for(int i = n ; i >= 1 ; -- i) printf("%lld\n",val2[i]) ;
return 0;
}```

View Code

CodeForces – 1013DChemical table

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10 ;
int fa[maxn] ;
int fi(int x)
{
return x == fa[x] ? fa[x] : fa[x] = fi(fa[x]) ;
}
int main(int argc, char const *argv[])
{
int n, m, q ;
int ans = 0 ;
scanf("%d %d %d",&n,&m,&q) ;
ans = m + n - 1 ;
for(int i = 0 ; i <= n+m+5+m ; ++ i) fa[i] = i ;
for(int i = 1, x, y ; i <= q ; ++ i)
{
scanf("%d %d",&x,&y) ;
y += m+n ;
int fx = fi(x) ;
int fy = fi(y) ;
if(fx != fy)
{
fa[fy] = fx ;
ans -- ;
}
}
printf("%d\n",ans) ;
return 0;
}```

View Code

CodeForces – 1131DChemical table

```#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4 + 10 ;
const int maxn = 1e3 + 10 ;
#define pii pair<int,int>
char mp[maxn][maxn] ;
int fa[maxn*2] ;
int vis[maxn*2] ;
set<int> se ;
vector<int> ve[maxn*2] ;
int du[maxn*2] ;
int ans[maxn*2] ;
int Find(int x)
{
return x == fa[x] ? fa[x] : fa[x] = Find(fa[x]) ;
}
void merge(int x, int y)
{
int fx = Find(x), fy = Find(y) ;
if(fx != fy)
{
fa[fx] = fy ;
}
}
int main(int argc, char const *argv[])
{
int n, m ;
se.clear() ;
memset(vis,0,sizeof vis) ;
memset(ans,0,sizeof ans) ;
scanf("%d %d",&n,&m) ;
for(int i = 1 ; i <= m+n ; ++ i) fa[i] = i, du[i] = 0 ;
for(int i = 1 ; i <= n ; ++ i)
{
scanf("%s",mp[i]+1) ;
for(int j = 1 ; j <= m ; ++ j) if(mp[i][j] == '=') merge(i,j+n) ;
}

for(int i = 1 ; i <= n ; ++ i)
{
for(int j = 1 ; j <= m ; ++ j)
{
if(mp[i][j] == '=') merge(i,j+n) ;
}
}
for(int i = 1 ; i <= n ; ++ i)
{
for(int j = 1 ; j <= m ; ++ j)
{
if(mp[i][j] == '>') ve[Find(j+n)].push_back(Find(i)), du[Find(i)] ++ ;
else if(mp[i][j] == '<') ve[Find(i)].push_back(Find(j+n)) , du[Find(j+n)] ++ ;
}
}
stack<int> st ;
for(int i = 1 ; i <= n + m ; ++ i)
{
if(du[Find(i)] == 0 && vis[Find(i)] == 0)
{
vis[Find(i)] = 1 ;
st.push(Find(i)) ;
ans[Find(i)] = 1 ;
}
}
while(!st.empty())
{
int u = st.top() ;
st.pop() ;
for(int i = 0 ; i < ve[u].size() ; ++ i)
{
int v = ve[u][i] ;
du[Find(v)] -- ;
if(du[Find(v)] == 0  && vis[Find(v)] == 0)
{
st.push(Find(v)) ;
vis[Find(v)] = 1 ;
ans[Find(v)] = ans[Find(u)] + 1 ;
}
}
}
for(int i = 1 ; i <= n + m ; ++ i)
{
if(vis[Find(i)] == 0)
{
printf("NO\n") ;
return 0 ;
}
}
printf("YES\n") ;
for(int i = 1 ; i <= n ; ++ i) printf("%d%c",ans[Find(i)]," \n"[i == n]) ;
for(int i = n + 1 ; i <= n + m ; ++ i) printf("%d%c",ans[Find(i)]," \n"[i == n]) ;
return 0;
}```

View Code

CodeForces – 1166E Chemical table

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10 ;
int arr[55][maxn] ;
int vis[550][maxn] ;
int main(int argc, char const *argv[])
{
int m, n ;
scanf("%d %d",&m,&n) ;
memset(vis,0,sizeof vis) ;
for(int i = 1, cnt ; i <= m ; ++ i)
{
scanf("%d",&cnt) ;
arr[i][0] = cnt ;
for(int j = 1 ; j <= cnt ; ++ j) scanf("%d",&arr[i][j]), vis[i][arr[i][j]] = 1 ;
}
int flag = 0 ;
for(int i = 1 ; i <= m ; ++ i)
{
for(int j = 1 ; j <= m ; ++ j)
{
flag = 0 ;
for(int k = 1 ; k <= n ; ++ k)
{
if(vis[i][k] && vis[j][k]) flag = 1 ;
}
if(flag == 0)
{
printf("impossible\n") ;
return 0 ;
}
}
}
printf("possible\n") ;
return 0;
}```

View Code

```#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 10 ;
const int mod = 300 ;
int ans = 0 ;
int fa[maxn], sum[maxn] ;
int fi(int x)
{
if(fa[x] != x)
{
int root = fa[x] ;
fa[x] = fi(fa[x]) ;
sum[x] = sum[root] + sum[x] ;
}
return fa[x] ;
}
int main(int argc, char const *argv[])
{
int n, m ;

while(scanf("%d %d",&n,&m) != EOF)
{
ans = 0 ;
for(int i = 1 ; i <= n ; ++ i) fa[i] = i, sum[i] = 0 ;
for(int i = 1, x, y, s ; i <= m ; ++ i)
{
scanf("%d %d %d",&x,&y,&s) ;
int fx = fi(x), fy = fi(y) ;
if(fx == fy)
{
if(s != sum[x] - sum[y]) ans ++ ;
}
else
{
fa[fx] = fy ;
sum[fx] = s - sum[x] + sum[y] ;
}
}
printf("%d\n",ans) ;
}

return 0;
}```

View Code

<