Thứ Tư, 18 tháng 11, 2020

Cho n chất hóa học và m cặp trong số chúng có thể phản ứng với nhau. Mỗi lần 2 chất phản ứng với nhau thì độ nguy hiểm tăng gấp đôi !

 Đề bài: $\href{https://codeforces.com/problemset/problem/445/B}{Đây}$

Tóm tắt: Cho n chất hóa học và m cặp trong số chúng có thể phản ứng với nhau. Mỗi lần 2 chất phản ứng với nhau thì độ nguy hiểm tăng gấp đôi !

Lời giải: Từ đây ta quy về bài toán đếm thành phần liên thông, và đáp án là $2^{n-v}$ trong đó v là số thành phần liên thông.

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maxn 55
  5. ll fa[maxn];
  6. ll root(ll x){
  7. if(fa[x]!=x) fa[x]=root(fa[x]);
  8. return fa[x];
  9. }
  10. int main(){
  11. ll i,n,m;
  12. cin>>n>>m;
  13. for(i=1;i<=n;i++) fa[i]=i;
  14. for(i=1;i<=m;i++){
  15. ll u,v;
  16. cin>>u>>v;
  17. fa[root(u)]=root(v);
  18. }
  19. ll ans = (ll)(1LL<<n);
  20. for(int i=1;i<=n;i++)
  21. if(root(i)==i) ans/=2;
  22. printf("%lld",ans);
  23. return 0;
  24. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...