Metal Steak

Hard to eat

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  0 Posts :: 79 Stories :: 0 Comments :: 0 Trackbacks

公告

aaaaaaaaaaaa

常用链接

留言簿(1)

我参与的团队

搜索

  •  

最新评论

#include <iostream>
using namespace std;

template 
< class Type >
struct
DisjointSet
{

    Type father[
10001];
    DisjointSet( 
const int n )
    {
        
forint i = 1; i <= n; i++ )
            father[i] 
= i;
    }
    DisjointSet()
    {
        
forint i = 1; i <= 10000; i++ )
            father[i] 
= i;
    }
    Type
    getFather( 
const Type x )
    {
        Type t 
= x;
        
while( father[t] != t )
            t 
= father[t];
        Type tt 
= x;
        
while( father[tt] != tt )
        {
            
int tx = father[tt];
            father[tt] 
= t;
            tt 
= tx;
        }
        
return t;
    }
    
void
    mergeElement( 
const Type x, const Type y )
    {
        Type
        fx 
= getFather( x ), fy = getFather( y );
        
if( fx != fy )
            father[fy] 
= fx;
    }
    
bool
    judgeElement( 
const Type x, const Type y )
    {
        
if( getFather( x ) == getFather( y ) )
            
return true;
        
else
            
return false;
    }
};

int
main()
{
    
int
    n, m, o;
    cin 
>> n >> m >> o;
    DisjointSet 
< int > intds( n );
    
forint i = 1; i <= m; i++ )
    {
        
int x, y;
        cin 
>> x >> y;
        intds.mergeElement( x, y );
    }
    
forint i = 1; i <= o; i++ )
    {
        
int x, y;
        cin 
>> x >> y;
        
if( intds.judgeElement( x, y ) )
            cout 
<< "Yes" << endl;
        
else
            cout 
<< "No" << endl;
    }

    
return 0;
}

posted on 2009-09-15 21:28 mad4alcohol 阅读(378) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理