Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define maxn 55
- ll fa[maxn];
- ll root(ll x){
- if(fa[x]!=x) fa[x]=root(fa[x]);
- return fa[x];
- }
- int main(){
- ll i,n,m;
- cin>>n>>m;
- for(i=1;i<=n;i++) fa[i]=i;
- for(i=1;i<=m;i++){
- ll u,v;
- cin>>u>>v;
- fa[root(u)]=root(v);
- }
- ll ans = (ll)(1LL<<n);
- for(int i=1;i<=n;i++)
- if(root(i)==i) ans/=2;
- printf("%lld",ans);
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét