连通性判断

试题描述

无向图，包含n个节点编号1至n，初始没有边。

    现在逐次向图中添加m条边，你需要在添加边之前判断该两点是否连通。

输入

第一行两个正整数n、m。
接下来m行，每行两个正整数x、y。

输出

m行，每行包含一个整数0或1，0表示添加这条边之前两个点不连通，1表示连通。

输入示例

4 5
1 2
1 3
2 3
4 4
3 4

输出示例

0
0
1
1
0

其他说明

n,m<=300000。

#include <iostream>

using namespace std;
int f[301010];
int find(int a)   //找根节点 
{
    if(f[a]==a) return f[a];
    f[a]=find(f[a]);
    return f[a];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;  //初始化 
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(find(x)==find(y)) printf("1
");   //两个点的根节点相等，说明他们连同 
        else 
        {
            printf("0
");
            f[find(x)] = find(y);  //在find的过程中，会把x这一条线全部更新为以y的根节点为根节点的顶点 
        }
    }
    //system("pause");
    return 0;
}