zcmu 1900: Problem D: Dominos（单向并查集）-白红宇

zcmu 1900: Problem D: Dominos（单向并查集）

阅读量：3899 次

发布时间：2019-05-23

本文共 2288 字，大约阅读时间需要 7 分钟。

【题目】

Problem D: Dominos

Dominos are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominos falling again.

Your task is to determine, given the layout of some domino tiles, the minimum number of dominos that must be knocked down by hand in order for all of the dominos to fall.

Input

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing two integers, each no larger than 100 000. The first integer n is the number of domino tiles and the second integer m is the number of lines to follow in the test case. The domino tiles are numbered from 1 to n. Each of the following lines contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well.

Output

For each test case, output a line containing one integer, the minimum number of dominos that must be knocked over by hand in order for all the dominos to fall.

Sample Input

13 21 22 3

Sample Output

【题意】

给定测试数据组数，每组给定牌数n和m对相连的牌(牌从1-n)，给定x,y，x倒了下一张牌y也会倒，问需要推多少次使所有的牌都倒下。

【思路】

第一眼以为是普通并查集，写好提交，wa了。然后才发现，题目要求的是单向的，而并查集是双向的qaq。

如：3 2

1 2

3 2

正确答案应该是2，而直接使用并查集的结果是1。因此我们需要考虑到没有出现父节点的牌。又考虑到：

如：3 3

1 2

3 2

3 3

这种情况。因此我们需要比较下并查集的集合数与没有父节点的牌数，并输出较大值。

【代码】

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define mem(a,b) memset(a,b,sizeof(a))#define Pi acos(-1)#define eps 1e-8using namespace std;typedef long long int ll;#define mem(a) memset(a,0,sizeof(a))int pre[100005],vis[100005];int Find(int x) //寻找父节点{ return x==pre[x]?x:pre[x]=Find(pre[x]);}int join(int x,int y) //更新集合{ x=Find(x),y=Find(y); if(x!=y) pre[y]=x;}main(){ int t,n,m,x,y; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); mem(vis); for(int i=1;i<=n;i++) pre[i]=i; while(m--) { scanf("%d%d",&x,&y); vis[y]=1; //记录拥有父节点的牌 join(x,y); } int c=0,cc=0; for(int i=1;i<=n;i++) { if(pre[i]==i) c++; if(!vis[i]) cc++; } printf("%d\n",max(c,cc)); }}

转载地址：http://syben.baihongyu.com/

你可能感兴趣的文章