Metal Steak

Hard to eat

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

公告

aaaaaaaaaaaa

常用链接

留言簿(1)

我参与的团队

搜索

  •  

最新评论

#include <iostream>
using namespace std;

struct
DisjointSet
{
    
int
    father[
1001], ncnt;
    DisjointSet( 
const int x )
    {
        memset( father, 
0sizeof father );
        
forint i = 1; i <= x; i++ )
            father[i] 
= i;
        ncnt 
= x;
    }
    DisjointSet()
    {
        memset( father, 
0sizeof father );
        
forint i = 1; i <= 1000; i++ )
            father[i] 
= i;
        ncnt 
= 1000;
    }
    
int
    getFather( 
int x )
    {
        
if( father[x] == x )
            
return father[x];
        
else
        {
            
int fx = getFather( father[x] );
            father[x] 
= fx;
            
return father[x];
        }
    }
    
void
    merge( 
const int x, const int y )
    {
        
if( getFather( x ) != getFather( y ) )
            father[getFather( x )] 
= getFather( y );
    }
    
bool
    judge( 
const int x, const int y )
    {
        
if( getFather( x ) == getFather( y ) )
            
return true;
        
else
            
return false;
    }
    
int
    count()
    {
        
int
        a[
1001= { 0 }, cnt = 0;
        
forint i = 1; i <= ncnt; i++ )
            
if( father[i] == i )
                a[i]
++;
        
forint i = 1; i <= ncnt; i++ )
            
if( a[i] )
                cnt
++;
        
return cnt;
    }
};

int
main()
{
    
int n, enemy[1001= { 0 }, m;
    cin 
>> n >> m;
    DisjointSet friends( n );
    
forint i = 1; i <= m ; i++ )
    {
        
char f;
        
int
        x, y;
        cin 
>> f >> x >> y;
        
if( f == 'F' )
            friends.merge( x, y );
        
if( f == 'E' )
        {
            
if( enemy[x] == 0 )
                enemy[x] 
= y;
            
else
                friends.merge( enemy[x], y );
            
if( enemy[y] == 0 )
                enemy[y] 
= x;
            
else
                friends.merge( enemy[y], x );
        }
    }

    cout 
<< friends.count() << endl;

    
return 0;
}

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

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