• 欢迎光临~

P1551 亲戚

试解

``````#include "iostream"
#include <bits/stdc++.h>
using namespace std;
int n,m,p;
int fa[10010];
int myFind(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];}
void myUnion(int a,int b){fa[myFind(a)]= myFind(b);}
int main(){
cin>>n>>m>>p;
for(int i=1;i<=n;i++)fa[i]=i;
int x,y;
while(m--){
cin>>x>>y;
myUnion(x,y);
}
while(p--){
cin>>x>>y;
if(myFind(x)== myFind(y))cout<<"Yesn";
else cout<<"Non";
}
return 0;
}
``````

(A)

P1536 村村通

试解

``````#include "iostream"
#include <bits/stdc++.h>
using namespace std;
int fa[1010];
int myF(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];}
void myU(int a,int b){fa[myF(a)]=myF(b);}
int n,m;
bool vis[1010];
int main(){
while (true){
cin>>n;
if(!n)break;
cin>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
vis[i]= false;
}
int x,y;
while(m--){
cin>>x>>y;
myU(x,y);
}
int ans=0;

for(int i=1;i<=n;i++){
if(vis[myF(i)])continue;
vis[myF(i)]= true;
ans++;
}
cout<<ans-1<<endl;
}
}
``````

(A)

P3370 字符串哈希

喜欢的板子

``````#include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
int prime=233317;
ull mod=212370440130137957ll;

ull hashe(char s[])
{
int len=strlen(s);
ull ans=0;
for (int i=0;i<len;i++)
ans=(ans*base+(ull)s[i])%mod+prime;
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
a[i]=hashe(s);
}
sort(a+1,a+n+1);
for(int i=1;i<n;i++)
{
if(a[i]!=a[i+1])
ans++;
}
printf("%d",ans);
}
``````

P3405 Cities and States S

试解

``````#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int>ump[100005];
int n,ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
string a,b;
cin>>a>>b;
int A=a[0]*26+a[1];
int B=b[0]*26+b[1];
ans+=ump[B][A];
if(A==B)ans-=ump[A][B];
ump[A][B]++;
}
printf("%d",ans);
return 0;
}
``````