并查集 boj1034

冥王星的故事II-占领岛国 Submit: 849   Accepted:263 Time Limit: 2000MS  Memory Limit: 65536KDescription
经过几年的战争，在H上将的带领上，冥王星的勇士们攻克了地球人称作日本的岛国，Pluto的Boss级人物zhao0057决定在那里建立一个根据地。然而，战争过后，这个地方已经是一片废墟，要想把根据地重新建立起来，第一件事情就是修路，zhao0057命令他的参谋长moyuji负责道路的修建，moyuji认为这是很简单的工作，因此他并没有制定一个详细的计划，每到一处就随意的修建道路，然后又会发觉某条路没有规划好，需要把它拆除。经过多次的修建拆除，他自己都弄不清楚到底哪些城市互相连通了，哪些没有。所谓连通，是指至少能找到一条从a到b的路径。现在，moyuji希望你帮他设计一个程序解决这个问题。

Input
首先是两个整数n(n< 100)和m,n表示城市的数目.
接着有m行，每行有三个数 D a b (0< a,b <= n a!=b),如果D=0 表示连接a、b之间的道路。如果D=1,表示撤除a、b之间的道路。(0 < a,b <=n)
然后是一个整数q(q<10)，表示查询的次数。
接下来q行每行是两个整数a,b.表示询问a,b间是否连通

Output
对每次查询，如果a,b间是连通的输出yes，否则输出no

Sample Input

4 4
0 1 2
0 2 3
0 3 4
1 3 4
2
1 3
1 4

Sample Output

yes
no

Hint
moyuji先修建了三条道路1-2,2-3,3-4.然后又拆除了道路3-4.
这时候对于城市1,3。我们可以找到一条路径从1到3,即1-2-3。
而对于城市1，4。因为拆除了道路3-4，我们找不到一条这样的路径了。

 

 

比较简单的一个题，求图中的两个点是否可达(即属于同一个集合)

直接贴代码了

 

#include <cstdlib>
#include <iostream>

using namespace std;

int n, m, path[110][110], set[110];

void init()
{
     memset(path, 0, sizeof(path));
     memset(set, 0, sizeof(set));
}

int find_set(int a)
{
    if(a != set[a])
        set[a] = find_set(set[a]);
    return set[a];
}

int find(int a, int b)
{
    if(find_set(a) == find_set(b))
    {
        return true;
    }
    
    return false;
}

void union_set(int a, int b)
{
     set[find_set(a)] = find_set(b);
}

void make_set(int n)
{
     int i, j;
     for(i=1; i<=n; i++)
     {
         set[i] = i;
     }
     
     for(i=1; i<=n; i++)
     {
              for(j=i; j<=n; j++)
              {
                       if(0 == path[i][j])
                           continue;
 // printf("path:%d %d\n", i, j);

                       union_set(i, j);
              }
     }
}

int main(int argc, char *argv[])
{
    int D, a, b, i, q;
    scanf("%d %d", &n, &m);
    
    init();
    for(i=0; i<m; i++)
    {
             scanf("%d %d %d", &D, &a, &b);
             if(0 == D)
             {
                  path[a][b] = path[b][a] = 1;
             }
             else
             {
                  path[a][b] = path[b][a] = 0;
             }
    }
    
    make_set(n);
    /*
    for(i=1; i<=n; i++)
    {
             printf("%d ", set[i]);
    }
    printf("\n");
    */
    
    scanf("%d", &q);
    for(i=0; i<q; i++)
    {
             scanf("%d %d", &a, &b);
             if(find(a, b))
                 printf("yes\n");
             else
                 printf("no\n");
    }
    
    system("PAUSE");
    return EXIT_SUCCESS;
}