链接
来源：牛客网
题目描述：
The big day has fifinally arrived: today you are going to form groups of two in which you will do the end-of-the-year project. When you arrive at school, you learn that the teacher of the other class is sick, and that your teacher, Mr. B.A.P. Cee, will also have to make groups for the other class. Mr. B.A.P. Cee is a smart guy and realizes that he can use these unfortunate circumstances to his advantage.
Ending up with groups of one should be avoided at all cost, so mixing the students of the two classes may avoid this situation. However, while it is easy to pair up two students from the same class, it is more diffiffifficult to match up students from difffferen classes. Throughout the years there has been a lot of rivalry between the two groups, and many students dislike students in the other class. Mr. B.A.P. Cee knows which pairs of students will result in a fifight and a failed project.
You are given a list of pairs of students who cannot work together. How many disjoint groups of two can Mr. B.A.P. Cee make that will not result in a failed project?
输入描述:
The input consists of:
• A line with two integers n (1 ≤ n ≤ 105), the number of students, and m (0 ≤ m ≤ 2*105), the number of pairs of students who cannot work together.
• m lines, each with two distinct integers i and j (1 ≤ i, j ≤ n, i = j), giving a pair of students who cannot work together.
Students are identifified by the numbers 1 through n. It is guaranteed that it is possible to split the students into two classes in such a way that all students from the same class get along.
输出描述:
Output the number of pairs of students Mr. B.A.P. Cee can make without making any pair of students who cannot work together.
示例1
输入
3 2
1 2
3 1
输出
1
示例2
输入
5 6
1 4
2 4
3 4
1 5
2 5
3 5
输出
2
示例3
输入
6 6
1 4
2 5
3 6
1 5
3 5
2 6
输出
3
题意：
给出n个人，m个关系，其中这m个关系是按照
x y的方式给出的，表示这两个人之间不能连一条边，（不能建立联系）
其中一个点和其他的点建立联系之后，这个点就不能和其他的点建立联系
要求出的是，在这个点中，最多能够建立多少联系（这里的联系可以看作是婚姻）
思路1：
本以为可以采用匈牙利算法进行处理，没想到是题面不太规范，应该是105 而不是105，
思路2：就像在模拟染色一样，将不能建立联系的点之间，就不能染上相同的颜色，所以说，相邻的两个点，必然是两个不同的颜色，所以可以采用dfs来进行处理，在处理的过程中，可以判断与当前的染色是否有冲突，并进行下一步染色，（并没有按照这样的方法来进行处理）
思路3：
进行DFS，对不能建立联系的边进行处理，使得他们染上不同的颜色，最后判断染色为1的有多少个（假如为cnt1），判断染色为2的有多少个（假如为cnt2），判断cnt1 + cnt2 == n(点的总个数) && (cnt1 * cnt2 == m) 的情况，应该是有（cnt1/2 + cnt2/2）组情况；反之，可以建立n/2组情况
思路4：
看见巨巨有用并查集维护写的
附上官方题解：
附上华东交通大学题解：
出题人Ragnar代码：
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> done;
vector<vector<int>> g;
void dfs(int u, int p) {
if(done[u]) return;
done[u] = p;
for(auto v : g[u]) dfs(v, 3 - p);
}
int main() {
int n, m;
cin >> n >> m;
done.assign(n, 0);
g.resize(n);
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0, 1);
int s = count(begin(done), end(done), 1);
int t = count(begin(done), end(done), 2);
if(s + t == n and s * t == m)
cout << s / 2 + t / 2 << endl;
else
cout << n / 2 << endl;
}
出题人Timon代码：
#include <algorithm>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
void answer(int n) {
cout << n << endl;
exit(0);
}
void solve() {
int n, m;
cin >> n >> m;
vi deg(n);
for (int i = 0, u, v; i < m; ++i)
cin >> u >> v, --u, --v, deg[u]++, deg[v]++;
sort(deg.begin(), deg.end());
int a = deg[0], b = deg.back();
int ac = std::count(deg.begin(), deg.end(), a);
int bc = std::count(deg.begin(), deg.end(), b);
if (ac == n)
cout << ((2*a==n && a%2) ? (n-2)/2 : n/2) << endl;
else cout << ((ac+bc==n && a==bc && ac==b && a%2 && b%2) ? (n-2)/2 : n/2) << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout << fixed << setprecision(12);
solve();
return 0;
}
某巨巨用并查集写的代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int fa[2*N],n,m,ans;
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}
int main(){
cin>>n>>m;
if(n==1){
cout<<0;
return 0;
}
for(int i=1;i<=2*n;i++)fa[i]=i;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
int fu=find(u),fv=find(v),fu_=find(u+n),fv_=find(v+n);
if(fu_<=n)fa[fv]=fu_;else fa[fu_]=fv;
if(fv_<=n)fa[fu]=fv_;else fa[fv_]=fu;
}
int a=fa[1],cnta=0,cntb=0;
for(int i=1;i<=n;i++){
if(fa[i]==a)cnta++;
else cntb++;
}
ans=cnta/2+cntb/2;
if(cnta%2==1&&cntb%2==1&&cnta*cntb!=m)ans++;
cout<<ans;
}
my_code1 :
const int maxn = 2e5 + 7;
int n, m;
vector<int> vet[maxn];
ll col[maxn];
void get(int u, int colour) {
if (col[u]) return;
else {
col[u] = colour;
for (auto it : vet[u]) {
get(it, 3 - colour);
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u = read, v = read;
u--; v--;
vet[u].push_back(v);
vet[v].push_back(u);
}
get(0, 1);
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i++) {
if (col[i] == 1) cnt1++;
else if (col[i] == 2) cnt2++;
}
if (cnt1 + cnt2 == n && cnt1 * cnt2 == m) {
cout << ((cnt1 / 2 + cnt2 / 2)) << endl;
}
else cout << (n / 2) << endl;
Accepted;
}
my_code 2:
大同小异罢了
#define Accepted return 0
const int maxn = 2e5 + 7;
int head[maxn], col[maxn];
int cnt = 0;
int n, m;
struct node {
int to, nex;
}e[maxn<<1];
void init() {
for (int i = 0; i <= n; i++) {
head[i] = -1;
}
cnt = 0;
}
void add(int u, int v) {
e[cnt].to = v;
e[cnt].nex = head[u];
head[u] = cnt++;
}
void get(int u, int colour) {
if (col[u]) return;
else {
col[u] = colour;
for (int i = head[u]; ~i; i = e[i].nex) {
get(e[i].to, 3 - colour);
}
}
}
int main()
{
cin >> n >> m;
init();
for (int i = 1; i <= m; i++) {
int u = read, v = read;
add(u, v);
add(v, u);
}
get(1, 1);
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++) {
if (col[i] == 1) cnt1++;
else if (col[i] == 2) cnt2++;
}
if (cnt1 + cnt2 == n && cnt1 * cnt2 == m) {
cout << ((cnt1 / 2 + cnt2 / 2)) << endl;
}
else cout << (n / 2) << endl;
Accepted;
}