1 solutions
-
0
讲道理这个题数据有问题但是还是能过,第一个数据里面
自己肯定不能和自己是敌人但是不影响大部分人过题 这种敌人的敌人是朋友的题有一种方法叫并查集反集其实就两行代码 比如a和b是敌人a和c也是敌人那么b和c就是朋友处理这种情况用反集很简单 只需要合并n+b和a,n+a和b;合并n+c和a,n+a和c;这样b和c就合并了,看代码好理解
#include<bits/stdc++.h> using namespace std; int ans,n,m,a,b,f[2500];//反集开双倍 char op; int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } void uni(int a,int b){ f[find(a)]=find(b); } int main(){ cin>>n>>m; for(int i=1;i<=2*n;i++) f[i]=i;//反集双倍初始化 for(int i=1;i<=m;i++){ cin>>op>>a>>b; if(op=='F') uni(a,b); else{ uni(n+a,b);//反集合并 uni(n+b,a); } } for(int i=1;i<=n;i++) if(f[i]==i)ans++; cout<<ans; }
- 1
Information
- ID
- 1534
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 30
- Accepted
- 12
- Uploaded By