[BZOJ1370][Baltic2003]Gang团伙并查集+拆点

Description

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、我朋友的朋友是我的朋友； 2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

Input

第1行为n和m，N小于1000,M小于5000；以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。

Output

一个整数，表示这n个人最多可能有几个团伙。

Sample Input

6
4
E 1 4
F 3 5
F 4 6
E 1 2

Sample Output

HINT

{1},{2,4,6},{3,5}

Solution

做法：并查集+拆点

朋友的朋友是我的朋友很好解决，直接并掉两个集合

关键是敌人的敌人就是我的朋友。

这个条件用拆点来解决

假设$x,y$敌对，将$x$和$y+n$这两个集合还有$y$,$x+n$这两个集合并起来就可以了

为什么要这样呢？

假设$a,b$为敌，$b,c$为敌，这样就可以把$a,c$并起来了

另外要注意细节，比如初始化$f[i]$要$for$到$2n$，跑完$m$个关系后要再重新跑一遍

#include <bits/stdc++.h>

using namespace std ;

#define N 5000

int n , m ;

int f[ N ] , a[ N ] ;

int find( int x ) {

    if( f[ x ] == x ) {

        return x ;

    }return f[ x ] = find( f[ x ] ) ;

}

int main() {

    scanf( "%d%d" , &n , &m ) ;

    for( int i =  ; i <=  * n ; i ++ ) f[ i ] = i ;

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

        char ch[  ] ;

        int x , y ;

        scanf( "%s%d%d" , ch , &x , &y ) ;

        if( ch[  ] == 'F' ) f[ find( y ) ] = find( x ) ;

        else {

            f[ find( y + n ) ] = find( x ) ;

            f[ find( x + n ) ] = find( y ) ;

        }

    }

    int ans =  ;

    for( int i =  ; i <= n ; i ++ ) f[ i ] = find( i ) ;

    sort( f +  , f + n +  ) ;

    for( int i =  ; i <= n ; i ++ ) {

        if( f[ i ] != f[ i -  ] ) ans ++ ;

    }

    printf( "%d\n" , ans ) ;

}

巴特西

[BZOJ1370][Baltic2003]Gang团伙并查集+拆点

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

做法：并查集+拆点

最新文章

热门文章

巴特西

[BZOJ1370][Baltic2003]Gang团伙 并查集+拆点

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

做法：并查集+拆点

最新文章

热门文章

[BZOJ1370][Baltic2003]Gang团伙并查集+拆点