T3题解

发表于 | 评论数： | 阅读次数：

一道看似是图论又不是图论的题（出数据的人太懒就1个数据点）
定义：如果一个点的度为奇数，那么称这个点为奇点
小学奥数：如果一个图有0或2个奇点，那么这个图可以一遍走过所有的道路而不重复，否则需加上(奇点的个数-2)/2条边可以一遍走过所有的道路而不重复
所以代码就很简单了
Source:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100010;
int a[MAXN],n,cnt,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        a[x]++;
        a[y]++;
    }
    for(int i=1;i<=n;i++){
        if(a[i]%2==1) cnt++;
    }
    if(cnt==0||cnt==2) cout<<"fuckccf";
    else {cout<<"ccf_is_a_shit"<<endl;
    cout<<(cnt-2)/2;}
    return 0;
}