题意是一次装入物品,物品由两种元素组成,当遇到即将装入的物品与已经装入的物品形成k个物品,k种元素,跳过该物品的装入。可以将每种元素看成顶点,物品看成一条边。这样问题就转化为利用并查集求环的情况。
算法竞赛训练指南中的代码:
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pb push_back
#define in freopen("in.txt", "r", stdin);
#define out freopen("out.txt", "w", stdout);
#define print(a) printf("%d\n",(a));
#define bug puts("********))))))");
#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii,int> VII;
typedef vector<int>:: iterator IT; #define N (int)(1e5+100)
int pa[N], rank[N];
void init(void)
{
for(int i = ; i < N; i++)
pa[i] = i;
memset(rank, , sizeof(rank));
}
void merge(int x, int y)
{
if(rank[x] > rank[y])
pa[y] = x;
else {
pa[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
}
int findset(int x)
{
return (pa[x] == x) ? x: pa[x] = findset(pa[x]);
}
int main(void)
{
int x, y;
while(~scanf("%d", &x))
{
int cnt = ;
init();
while(x != -)
{
scanf("%d", &y);
x = findset(x), y = findset(y);
if(x == y)
cnt++;
else merge(x, y);
scanf("%d", &x);
}
printf("%d\n", cnt);
}
return ;
}