LightOJ 1009 二分图染色+BFS/种类并查集

**题意：**有两个阵营的人，他们互相敌对，给出互相敌对的人，问同个阵营的人最多有多少个。
**思路：**可以使用种类并查集写。也可以使用使用二分图染色的写法，由于给定的点并不是连续的，所以排序离散化一下，再进行BFS染色。

二分图：

/** @Date    : 2016-11-19-21.46


  * @Author  : Lweleth (SoungEarlf@gmail.com)


  * @Link    : https://github.com/


  * @Version :


  */


#include <stdio.h>


#include <iostream>


#include <string.h>


#include <algorithm>


#include <utility>


#include <vector>


#include <map>


#include <set>


#include <string>


#include <stack>


#include <queue>


//#include<bits/stdc++.h>


#define LL long long


#define MMF(x) memset((x),0,sizeof(x))


#define MMI(x) memset((x), INF, sizeof(x))


using namespace std;





const int INF = 0x3f3f3f3f;


const int N = 2e4+20;








int vis[N];


bool mp[N];


vector<int> ed[N*10];


int c[N][2];


int s[N*10];





int a[N*10];


int b[N*10];





void bfs(int s, int v)


{


    queue<int>q;


    vis[s] = 1;


    q.push(s);


    while(!q.empty())


    {


        int nw = q.front();


        q.pop();


        c[v][vis[nw]]++;


        for(int i = 0; i < ed[nw].size(); i++)


        {


            int nx = ed[nw][i];


            if(vis[nx] == -1)


            {


                vis[nx] = vis[nw]^1;


                q.push(nx);


            }


        }


    }


}











int main()


{


    int T;


    int cnt = 0;


    cin >> T;


    while(T--)


    {


        int n;


        scanf("%d", &n);


        MMF(mp);


        MMF(s);


        int ct = 0;


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


        {


            scanf("%d%d", a + i, b + i);


            if(!mp[a[i]])


                mp[a[i]] = 1, s[++ct] = a[i];


            if(!mp[b[i]])


                mp[b[i]] = 1, s[++ct] = b[i];


        }


        for(int i = 1; i <= ct; i++)


        {


            ed[i].clear();


            vis[i] = -1;


            c[i][0] = c[i][1] = 0;


        }


        sort(s + 1, s + ct + 1);


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


        {


            int x = upper_bound(s + 1, s + 1 + ct, a[i]) - s - 1;


            int y = upper_bound(s + 1, s + 1 + ct, b[i]) - s - 1;


            ed[x].push_back(y);


            ed[y].push_back(x);


        }


        int vol = 0;


        for(int i = 1; i <= ct; i++)


        {


            if(vis[i]==-1)


                bfs(i, ++vol);


        }


        int ans = 0;


        for(int i = 1; i <= vol; i++)


            ans+=max(c[i][0],c[i][1]);


        printf("Case %d: %d\n", ++cnt, ans);


    }


    return 0;


}

巴特西

LightOJ 1009 二分图染色+BFS/种类并查集

最新文章

热门文章