西门吹牛的方法最好了,特别适合我这样的新手啊

其实也没学过并查集。

只是将KRUSKAL中判断两个结点是否在一个连通分量的思想用过来。

貌似那个就是并查集。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 10ms

├ 测试数据 09：答案正确... 70ms

├ 测试数据 10：答案正确... 90ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：170ms

比较经典的并查集，第一次提交没过，因为路径压缩错了，所以一定要记住压缩路径的函数！！

标准并查集

经典题目

无向图传递封包当然不行...N3...的...

这个当然只有...并...并...再并...没查的集拉....

无向图.两人有亲戚关系就令两人想通.要判断任意两个人之间有没有亲戚关系,就看这两个接点间能否相同,也就是计算图的传递闭包...

这样为什么不行>>???

计算图的传递闭包>?

有没有 再 详细 一点的

我是 初学者

能不能在2-10测试点中给一个?不然我都不知道我为什么自己是了那么多数据还会错...

并查集

初学者必做题

3个字

并差集...

最基本的并查集操作。

如果两个人之间有亲戚关系，则把两个人所在的集合并在一起，最后判断一下给定的两个人是否在一个集合中就可以了。

题目数据规模不是很大，放心做。（但是还是建议用森林来表示）

随便搞个数组标记一下就过了！！！！！

include <iostream>

include <cstdio>

include <cstring>

include <string>

using namespace std;
int a[5000];
int main ()
{
int n,m,p;
cin >> n >> m >> p;
for(int i = 1;i<=n;++i)
{
a[i] = i;
}

int k,l;

while(m--)
{
scanf("%d %d",&k,&l);
int p = a[k];
for(int i = 1;i<=n;++i)
{
if(a[i]==p) a[i] = a[l];
}

}
while(p--)
{
scanf("%d %d",&k,&l);
if(a[k]==a[l]) printf("Yes\n");
else printf("No\n");

}
return 0;
}

//
// Created by JimmyChen on 6/10/17.
//
#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

const int maxN = 9999999;

struct UnionFind_set{
    int N;
    int p[maxN];
    inline void init(int n){N = n; for(int i = 0 ; i <= N; ++i) p[i] = i;}
    inline int root(int i){for(;i != p[i]; i = p[i]) p[i] = p[p[i]]; return i;}
    inline void unite(int a, int b){p[root(b)] = root(a);}
    inline bool query(int a, int b){return root(a) == root(b);}
}relatives;

int main(){
    int n = 0, m = 0, p = 0;
    cin >> n >> m >> p;
    relatives.init(n);
    int a, b;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        relatives.unite(a, b);
    }
    for (int i = 0; i < p; i++){
        cin >> a >> b;
        if(relatives.query(a, b)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

用图的连通块来求

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main{
    static int n,m,p;
    static List<List<Integer>>list;
    static boolean vis[];
    static int belong[],blocks;
    public static void DFS(int now){
        for(int i=0;i<list.get(now).size();++i)
            if(!vis[list.get(now).get(i)]){
                vis[list.get(now).get(i)]=true;
                DFS(list.get(now).get(i));
                belong[list.get(now).get(i)]=blocks;
            }
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(new BufferedInputStream(System.in));
        int a,b;
        n=in.nextInt();
        m=in.nextInt();
        p=in.nextInt();
        list=new ArrayList<List<Integer>>();
        for(int i=0;i<=n;++i)
            list.add(new ArrayList<Integer>());
        while(m--!=0){
            a=in.nextInt();
            b=in.nextInt();
            list.get(a).add(b);
            list.get(b).add(a);
        }
        vis=new boolean[n+1];
        belong=new int[n+1];
        blocks=0;
        Arrays.fill(vis,false);
        Arrays.fill(belong,-1);
        for(int i=1;i<=n;++i)
            if(!vis[i]){
                belong[i]=blocks;
                DFS(i);
                blocks++;
            }
        while(p--!=0){
            a=in.nextInt();
            b=in.nextInt();
            if(belong[a]==belong[b])    System.out.println("Yes");
            else    System.out.println("No");           
        }
        in.close();
    }
}

。。楼下的都在写什么啊=_=
并查集模版题28行代码无压行解决啊？？

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int fa[10001];
int n,m,p;
inline int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)   fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        fa[get(x)]=get(y);
    }
    for(int i=1;i<=p;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(get(x)==get(y))  
            printf("Yes\n");else printf("No\n");
    }
}

#include<iostream>
using namespace std;

int f[5000];

int find(int x)
{
if(x==f[x])return x;
x=f[x];
return find(f[x]);
}

bool judge(int x,int y)
{
if(find(x)==find(y))return 1;
return 0;
}

void hebing(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)f[x]=y;
}
int main()
{
//freopen("s.txt","r",stdin);
int n,m,p,s=0,d=0,g=0,h=0;
cin>>n>>m>>p;
for(int i=0;i<5000;i++)
{
f[i]=i;
}
for(int i=0;i<m;i++)
{
cin>>s>>d;
hebing(s,d);
}
for(int i=0;i<p;i++)
{
cin>>g>>h;
if(judge(g,h)==1)cout<<"Yes"<<endl;else cout<<"No"<<endl;
}
}

什么叫水题。。明明就是已经不叫题了。。

#include<cstdio>
#include<iostream>
#include<cstring>
#define maxa 10000
using namespace std;
int f[maxa];
int fid(int x)
{
return f[x]==x?x:fid(f[x]);
}
void merge1(int x,int y)
{
int tt1 = fid(x);
int t2 =fid(y);
if(tt1!=t2)
{
f[tt1] =t2;
}
}
int main()
{
int n,m,p,i,x,y;
cin>>n>>m>>p;
for(i=1;i<=n;++i)
f[i] = i;
for(i=1;i<=m;++i)
{
cin>>x>>y;
merge1(x,y);
}
while(p--)
{
cin>>x>>y;
if(fid(x)==fid(y))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}