嗯。。都是些最最最基础的水题
直接模板就OK了。。 刚学的可以一做
1.洛谷 并查集模板
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 10005
#define M 200005
using namespace std;
int n,m,p;
int fa[M];
int findf(int x){
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
void merge(int x,int y){
fa[findf(x)]=findf(y);
}
void solve(){
scanf("%d%d",&n,&m);
int k,x,y;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&k,&x,&y);
if(k==1)
merge(x,y);
else {
if(findf(x)==findf(y))
printf("Y
");
else printf("N
");
}
}
}
int main(){
solve();
return 0;
}
2.vijos1034家族
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 5005
#define M 5005
using namespace std;
int n,m,p;
int fa[M];
int findf(int x){
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
void merge(int x,int y){
if(findf(x)!=findf(y))
fa[findf(x)]=findf(y);
}
void solve(){
scanf("%d%d%d",&n,&m,&p);
int x,y;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
merge(x,y);
}
for(int i=1;i<=p;i++){
scanf("%d%d",&x,&y);
if(findf(x)==findf(y)) printf("Yes
");
else printf("No
");
}
}
int main(){
solve();
return 0;
}
3.洛谷p1892团伙
#include<cstdio>
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,m;
int flag;
int f[2500];
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n*2;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
char t;int x,y;
cin>>t>>x>>y;
if(t=='F') f[find(x)]=find(y);
if(t=='E')
{
f[find(x+n)]=find(y);
f[find(y+n)]=find(x);
}
}
int s=0;
for(int i=1;i<=n;i++)
if(f[i]==i) s++;
printf("%d",s);
return 0;
}
4.洛谷p2078朋友
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 20005
#define M 20005
using namespace std;
int n,m,p,q;
int a[N],b[N];
int findf1(int x) {
return a[x]==x?x:a[x]=findf1(a[x]);
}
int findf2(int x) {
return b[x]==x?x:b[x]=findf2(b[x]);
}
void merge1(int x,int y) {
if(findf1(x)<findf1(y)) swap(x,y);
a[findf1(x)]=findf1(y);
}
void merge2(int x,int y) {
if(findf2(x)<findf2(y)) swap(x,y);
b[findf2(x)]=findf2(y);
}
int main() {
scanf("%d%d%d%d",&n,&m,&p,&q);
int x,y;
for(int i=1; i<=n; i++) a[i]=i;
for(int i=1; i<=m; i++) b[i]=i;
for(int i=1; i<=p; i++) {
scanf("%d%d",&x,&y);
merge1(x,y);
}
for(int i=1; i<=q; i++) {
scanf("%d%d",&x,&y);
merge2(-x,-y);
}
int cnta=0,cntb=0;
for(int i=1; i<=n; i++) {
if(findf1(1)==findf1(i)) cnta++;
}
for(int i=1; i<=m; i++) {
if(findf2(1)==findf2(i)) cntb++;
}
printf("%d",min(cnta,cntb));
return 0;
}5.洛谷p1547Out Of Hay
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define N 2005
#define M 10005
using namespace std;
int n,m;
int fa[N];
struct node{
int l,r,w;
}e[M];
bool cmp(node x,node y){
return x.w<y.w;
}
int findf(int x){
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
void merge(int x,int y){
fa[findf(x)]=findf(y);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].w);
sort(e+1,e+1+m,cmp);
int ans=0,tot=0;
for(int i=1;i<=m;i++){
int x=e[i].l;int y=e[i].r;
if(findf(x)!=findf(y))
{
merge(x,y);
ans=e[i].w;
tot++;
}
if(tot==n-1) break;
}
printf("%d",ans);
return 0;
}6.洛谷p1536村村通
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1005
#define M 10005
using namespace std;
int n,m;
int fa[N];
int findf(int x){
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
void merge(int x,int y){
fa[findf(x)]=findf(y);
}
int main(){
int tot=0;
while(1){
bool flag=0;
tot=0;
scanf("%d",&n);
if(n==0) break;
scanf("%d",&m);
memset(fa,0,sizeof(fa));
for(int i=1;i<=n;i++)
fa[i]=i;
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if(findf(x)!=findf(y)&&flag==0)
{
merge(x,y);
tot++;
}
if(tot==n-1)
flag=1;
}
printf("%d
",n-1-tot);
}
return 0;
}
7.洛谷p1396 营救(最小生成树+并查集)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define N 10005
#define M 20005
using namespace std;
int n,m,s,t;
int fa[N];
struct node{
int l,r,w;
}e[M];
void read(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].w);
}
bool cmp(node xx,node yy){
return xx.w<yy.w;
}
int findf(int x){
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
void merge(int x,int y){
fa[findf(x)]=findf(y);
}
int main(){
int ans=0,cnt=0;
read();
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
int x=e[i].l;
int y=e[i].r;
int w=e[i].w;
if(findf(x)!=findf(y)) {
cnt++;
merge(x,y);
ans=w;
}
if(findf(s)==findf(t)) break;
if(cnt==n-1) break;
}
printf("%d",ans);
return 0;
}
8.洛谷p1195口袋的天空
/*
P1195 口袋的天空
n个点 m条边 连成k个树的最小代价
若k为1 则连成一棵MST 跑一次kruskal n-1次连边
若 k为2 为最后的图必须为 两颗MST n-2次连边
同理 连成k个mst 进行 n-k次连边
若进行者n-k次操作中 没有了边 （即cpp中的 i<m) 直接输出 No Answer
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1005
#define M 10005
using namespace std;
int n,m,k;
int fa[N];
struct node{
int l,r,w;
}e[M];
int findf(int x){
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
void merge(int x,int y){
fa[findf(x)]=findf(y);
}
void read(){
scanf("%d%d%d",&n,&m,&k);
int x,y,t;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].w);
}
bool cmp(node xx,node yy){
return xx.w<yy.w;
}
int main(){
read();
for(int i=1;i<=n;i++)
fa[i]=i;
sort(e+1,e+1+m,cmp);
int tot=0,ans=0;
for(int i=1;i<=m;i++){
int x=e[i].l;
int y=e[i].r;
int w=e[i].w;
if(findf(x)!=findf(y)){
merge(x,y);
tot++;
ans+=w;
}
if(tot==n-k){
printf("%d",ans);
return 0;
}
}
printf("No Answer");
return 0;
}
9.洛谷P1111修复公路
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1005
#define M 100005
using namespace std;
int n,m;
int fa[N];
struct node{
int l,r,t;
}e[M];
int findf(int x){
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
void merge(int x,int y){
fa[findf(x)]=findf(y);
}
void read(){
scanf("%d%d",&n,&m);
int x,y,t;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].t);
}
bool cmp(node xx,node yy){
return xx.t<yy.t;
}
int main(){
read();
sort(e+1,e+1+m,cmp);
int tot=0;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
int x=e[i].l;
int y=e[i].r;
int t=e[i].t;
if(findf(x)!=findf(y)){
merge(x,y);
tot++;
}
if(tot==n-1){
printf("%d",t);
return 0;
}
}
printf("-1");
return 0;
}