## 【并查集+离散化】POJ2528

2528:Mayor’s posters

#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<stdio.h>
#include<iostream>
#include<set>
#include<map>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 10233;
pii q[100233 + 233];
int f[100233 + 233];
int ff(int x)
{
if(f[x] == x) return x;
return f[x] = ff(f[x]);
}
void uni(int u, int v)
{
f[ff(u)] = ff(v);
}
int main()
{
int tc,n;
scanf("%d",&tc);
for(int j = 1; j <= tc; j++)
{
scanf("%d",&n);
set<int> st;
unordered_map<int,int> raw,ump;
for(int i = 1; i <= n; i++)
{
int l,r;
scanf("%d%d",&l,&r);
q[i] = make_pair(l,r + 1);
st.insert(l);st.insert(r + 1);
}
for(int i = 1; i <= 100233; i++) f[i] = i;
int cnt = 0;
for(set<int>::iterator it = st.begin(); it != st.end(); it++)
{
ump[*it] = ++cnt;
//raw[cnt] = *it;
}
int ans = 0;
for(int i = n; i >= 1; i--)
{
int l = ump[q[i].first], r = ump[q[i].second];
if(ff(l) != ff(r))
{
int k = l;
while(ff(k) != ff(r))
{
k = ff(k);
f[k] = ff(r);
k = k + 1;
}
}
else ans++;
}
printf("%d\n",n - ans);
}
}