首页 > ACM题库 > HDU-杭电 > hdu 2636 Installing Software-并查集-[解题报告]C++
2014
02-12

hdu 2636 Installing Software-并查集-[解题报告]C++

Installing Software

问题描述 :

Installing software in Windows is a piece of cake: just download and install the software, then you can use it. Although installing a software in Linux only needs typing yum install thename in the command lines in some Linux distribution,especially Fedora/Red Hat,it requires a lot extra time in a process called resolving dependency(means the period of downloading the other packages it depends on in order to install itself completely and successfully).
The problem is designed like this:
Suppose Samuel needs to install software A,A depends on B,C,D,E,and Samuel has already installed package E in his system so in the command lines there only will appear the packages B,C,D,we can say it needs 3 packages to finish the installation.

输入:

The number of test cases t,each of the case has an integer m means m packages to depend on if want to install X successfully and completely. Then the next line will contain m(m<=26 the letters are A-Z only) letters represent the name of each packages. The an integer n(n<=26 the letters are A-Z only too),means n packages have been installed in the desktop of Samuel.

输出:

The number of test cases t,each of the case has an integer m means m packages to depend on if want to install X successfully and completely. Then the next line will contain m(m<=26 the letters are A-Z only) letters represent the name of each packages. The an integer n(n<=26 the letters are A-Z only too),means n packages have been installed in the desktop of Samuel.

样例输入:

3
3
A B C
2
A B
5
A B E D F
3
A B F
2
A B
2
A B

样例输出:

Samuel has to install another 1 package(s) in addition,the packages is/are C.
Samuel has to install another 2 package(s) in addition,the packages is/are E,D.
Samuel can install the software without installing anything else.

并查集需要注意几点 1初始化 2如果a和b已经在同一个集合中 不要重复添加,unionset之前需要检查 a与b是否已经插入

另外需要注意的是   如果x=findset(a); y=findset(b); 合并的时候 不是p[a]=b ; 而是 p[x]=y;!!!!!!!!!!!!!!!!!11


#include <stdio.h>

#include <iostream>

#include <string>

#include <iomanip>

#include <sstream>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <vector>

#include <map>

#include <memory.h>

using namespace std;

#define maxn 5555

int p[maxn];

int n,m,q;

int findset(int x){

    return p[x]==x? x:p[x]=findset(p[x]);

}


int main() {

    int a,b,x,y;

    while(scanf("%d%d%d",&n,&m,&q)==3){

        for(int i=1;i<=n;i++) p[i]=i;

        for(int i=1;i<=m;i++){

            scanf("%d%d",&a,&b);

            x=findset(a);

            y=findset(b);

            if(x!=y)  p[x]=y;

        }

        for(int i=1;i<=q;i++){

            scanf("%d%d",&a,&b);

            x=findset(a);

            y=findset(b);

            if(x!=y) printf("no\n");

            else printf("yes\n");

        }

    }

    return 0;

}

解题转自:http://hi.baidu.com/lbc123/item/ba7f7cfe339c3215cf9f3251


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish