2019河北省大学生程序设计竞赛（重现赛）J.舔狗

河北省大学生程序设计竞赛（重现赛）J.舔狗"/>

2019河北省大学生程序设计竞赛（重现赛）J.舔狗

题目链接：

解题心得：打比赛的时候队友告诉我是个奇偶环 d p dp dp，然后我们就怂了，事后补提发现是个贪心拓扑，心累。估计我写丑了吧不用输入挂会在 89 % 89\% 89%TLE

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;map <pair<int, int>, int>maps;int n, in_degree[maxn], cnt, cnt_single;//cnt记录配对的人数，cnt_single记录单身狗的数量
vector <int> ve[maxn];//存边//读入挂板子
namespace io {const int SIZE = 1e7 + 10;char inbuff[SIZE];char *l, *r;inline void init(){l = inbuff;r = inbuff + fread(inbuff, 1, SIZE, stdin);}inline char gc(){if(l == r) init();return (l != r) ? *(l++) : EOF;}void read(int &x){x = 0;char ch = gc();while(!isdigit(ch)) ch = gc();while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();}
}
using io::read;void init() {read(n);for(int i=1;i<=n;i++) {int v, u =i; read(v);if(u > v) swap(u, v);if(maps[make_pair(u, v)] == 1) continue;maps[make_pair(u, v)] = 1;ve[u].push_back(v);ve[v].push_back(u);in_degree[v]++;in_degree[u]++;}
}bool vis[maxn], in[maxn];//拓扑
void tp() {queue <int> qu;for(int i=1;i<=n;i++) {if(in_degree[i] == 1) {qu.push(i);in[i] = true;} else if(in_degree[i] == 0) {cnt_single++;}}while(!qu.empty()) {int now =qu.front(); qu.pop();if(vis[now]) continue;int u = -1;for(int i=0;i<ve[now].size();i++) {int v = ve[now][i];if(vis[v]) continue;else u = v;}if(u == -1) {continue;}vis[now] = true;vis[u] = true;cnt += 2;//写得头晕，不知道自己写的什么for(int i=0;i<ve[u].size();i++) {int v = ve[u][i];if(v == now) continue;if(vis[v]) continue;in_degree[v]--;if(in_degree[v] == 1) {if(in[v]) continue;else in[v] = true;qu.push(v);} else if(in_degree[v] == 0) {vis[v] = true;cnt_single++;}}}
}int main() {
//    freopen("1.in.txt", "r", stdin);init();tp();int res = n - cnt - cnt_single;cnt_single += (res&1);printf("%d\n", cnt_single);return 0;
}