题目描述
> “舔狗舔狗，
> 舔到最后，
> 一无所有。”
> 舔到最后，
> 一无所有。”
有 n 只舔狗，每只舔狗的心中都有自己朝思暮想的一位。
每个人虽然受到了一万次拒绝，还毅然第一万零一次鼓起勇气。
作为一个不食人间烟火的算法设计师，你早已看破红尘。但是，人世间的苦难仍让你挂念。看到众生在单恋中苦苦坚持，你决定普度众生，给大家找到一个最好的结局，让一无所有的舔狗尽量地少，让每个人都尽量能和自己喜欢的或喜欢自己的人修成正果。
也就是说，你需要给这 n 只舔狗配对，对于舔狗 i，他可以和他朝思暮想的人 aiai 配对。另外，喜欢 i 的其他舔狗也可以和他配对。你需要让没有被配对的舔狗尽量少。
输入描述:
第一行一个 n，表示舔狗个数。
第二行 n 个数字，第 i 个数字表示第 i只舔狗的朝思暮想的一位的编号 aiai。
2≤n≤1062≤n≤106
输出描述:
第一行一个数字，表示一无所有的舔狗的最小数量。
题目链接
就是一个无向图，问的是两两相邻的点匹配，最少会留下多少个没有匹配的点？
简单的分析一下，不难发现，我们可以看度，遇到度为1的点，那么在最贪心的选择，我们必须要去选择那个与它相邻的节点，同时，我们选了相邻的节点之后，要再把该节点所对出去的所有的点的度去更新了“-1”。然后，我们发现因为边的个数是N条，所以有可能存在环的。
怎么处理环的问题呢？我们可以用并查集，那些无法被访问到的节点一定是在环内的，所以我们在这里用到了并查集来维护一下，就可以维护那些在一个环内的个数，匹配数根据它的奇偶有关。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e6 + ;
int N, a[maxN], head[maxN], cnt, du[maxN], num[maxN], ans, root[maxN], sum[maxN], all[maxN];
int fid(int x) { return x == root[x] ? x : (root[x] = fid(root[x])); }
inline void mix(int x, int y)
{
int u = fid(x), v = fid(y);
if(u ^ v)
{
root[u] = v;
sum[v] += sum[u];
}
}
bool vis[maxN], used[maxN];
struct Eddge
{
int nex, to;
Eddge(int a=-, int b=):nex(a), to(b) {}
}edge[maxN<<];
inline void addEddge(int u, int v)
{
edge[cnt] = Eddge(head[u], v);
head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
queue<int> Q;
inline void tuopu()
{
while(!Q.empty())
{
int u = Q.front();
Q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i=head[u], v; ~i; i=edge[i].nex)
{
v = edge[i].to;
if(vis[v]) continue;
// du[v]--;
// if(du[v] == 1)
// {
// vis[v] = true;
// Q.push(v);
// num[v] = num[u] ^ 1;
// }
ans++; vis[v] = true;
for(int j=head[v], kk; ~j; j=edge[j].nex)
{
kk = edge[j].to;
if(!vis[kk])
{
du[kk]--;
if(du[kk] == )
{
//vis[kk] = true;
Q.push(kk);
}
}
}
break;
}
}
}
inline void init()
{
cnt = ans = ;
memset(head, -, sizeof(head));
memset(vis, false, sizeof(vis));
memset(num, , sizeof(num));
memset(used, false, sizeof(used));
memset(du, , sizeof(du));
memset(a, , sizeof(a));
memset(all, , sizeof(all));
for(int i=; i<=N; i++) { sum[i] = ; root[i] = i; }
while(!Q.empty()) Q.pop();
}
int main()
{
scanf("%d", &N);
init();
for(int i=, v; i<=N; i++)
{
scanf("%d", &v);
a[i] = v;
if(a[v] == i) continue;
du[i]++; du[v]++;
_add(i, v);
mix(i, v);
}
if(N == ) { printf("%d\n", ); return ; }
for(int i=; i<=N; i++)
{
if(du[i] == )
{
//vis[i] = true;
Q.push(i);
}
}
tuopu();
ans <<= ;
for(int i=; i<=N; i++)
{
int u = fid(i);
// if(!vis[i] && !used[u])
// {
// ans += ((int)(sum[u]/2)) * 2;
// used[u] = true;
// }
if(!vis[i]) all[u]++;
}
for(int i=; i<=N; i++) ans += ((int)(all[i]/)) * ;
printf("%d\n", N - ans);
return ;
}
/*
6
4 1 1 5 6 4
ans = 2
*/