bzoj 4874: 筐子放球

4874: 筐子放球

Time Limit: 10 Sec Memory Limit: 256 MB

Description

小N最近在研究NP完全问题，小O看小N研究得热火朝天，便给他出了一道这样的题目：

有 n 个球，用整数 1 到 n 编号。还有 m 个筐子，用整数1到m编号。

每个球只能放进特定的两个筐子之一，第 i 个球可以放进的筐子记为 Ai 和 Bi 。

每个球都必须放进一个筐子中。

如果一个筐子内有奇数个球，那么我们称这样的筐子为半空的。

求半空的筐子最少有多少个。

小N看到题目后瞬间没了思路，站在旁边看热闹的小I嘿嘿一笑："水题！"

然后三言两语道出了一个多项式算法。

小N瞬间就惊呆了，三秒钟后他回过神来一拍桌子：

"不对！这个问题显然是NP完全问题，你算法肯定有错！"

小I浅笑："所以，等我领图灵奖吧!"

小O只会出题不会做题，所以找到了你--请你对这个问题进行探究，并写一个程序解决此题。

Input

第一行两个整数 n，m

接下来 n 行，第 i + 1 行有两个整数 Ai ， Bi ，表示第 i 个球可以放的两个筐子。保证 Ai 不等于 Bi

1 <= n，m <= 2 * 10^5，1 <= Ai，Bi <= m

Output

第一行一个整数表示半空的筐子的最小值。

Sample Input

4 3
1 2
2 3
1 3
1 2

Sample Output

0
1，3 号球都放在 1 号筐子，2，4 号球都放在 2 号筐子。

HINT

各位不妨考虑下，如果要求输出方案应该怎么写.

Source

好巧妙的思维题

我们可以把筐子看成点，球当边

然后求一下连通块，含奇数条边的连通块个数即为答案

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define ll long long

#define N 400010

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int to[N],lj[N],fro[N],cnt;

void add(int a,int b){fro[++cnt]=lj[a];to[cnt]=b;lj[a]=cnt;}

bool vs[N];

int dfs(int x)

{

    vs[x]=;int tp=;

    for(int i=lj[x];i;i=fro[i])

    {

        tp++;

        if(!vs[to[i]]) tp+=dfs(to[i]);

    }

    return tp;

}

int n,m,x,y,ans;

int main()

{

    n=read();m=read();

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

    {

        x=read();y=read();

        add(x,y);add(y,x);

    }

    int tp;

    for(int i=;i<=m;i++) if(!vs[i])

    {

        tp=dfs(i)>>;

        if(tp&) ans++;

    }

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

    return ;

}

秒客网