题解 P1636 【Einstein学画画】
洛谷P1636 Einstein学画画(欧拉图)
个人认为这道题的数据有些问题
分析
这道题就是一个简单的欧拉回路的模板，统计每个点的度数，如果每个点的度数都为偶数，那么就可以一笔画(因为每个点都有进有出)，否则统计度数为奇数的点的个数(记为num)答案就是num/2(每次都把度数为奇数的点分别作为起点和终点)。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,dg[1010],a,b,num=0;
//dg记录每个点的度数
bool map[1010][1010];
//用邻接矩阵储存图
long long read()//快读
{
long long ans=0;
char ch=getchar(),last=' ';
while(ch<'0'||ch>'9')
{last=ch;ch=getchar();}
while(ch>='0'&&ch<='9')
{ans=ans*10+ch-'0';ch=getchar();}
if(last=='-')ans=-ans;
return ans;
}
void add(int x,int y)//加入
{
dg[x]++;dg[y]++;
map[x][y]=map[y][x]=true;
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
a=read();b=read();
add(a,b);
}
for(int i=1;i<=n;i++)
if(dg[i]&1==1)num++;
if(num==0||num==2)cout<<"1";
else cout<<num/2;
return 0;
}However
根据数据来看，这道题并未考虑该图是否为连通图，如果不连通，需要找到每一版块画的次数再累加。
这里还有一个小技巧，就是统计奇数偶数可以用bool数组存，每次取反，省空间
正确代码(54分qwq)：
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,fa[1010],cnt[1010]={0},ans=0;
bool dg[1010],visit[1010];
long long read()//快读
{
long long ans=0;
char ch=getchar(),last=' ';
while(ch<'0'||ch>'9')
{last=ch;ch=getchar();}
while(ch>='0'&&ch<='9')
{ans=ans*10+ch-'0';ch=getchar();}
if(last=='-')ans=-ans;
return ans;
}
int get(int k)//寻找根节点
{
if(fa[k]==k)return k;
else return fa[k]=get(fa[k]);
}
void Union(int x,int y)//合并
{
fa[get(x)]=get(y);
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
a=read();b=read();
dg[a]=!dg[a];dg[b]=!dg[b];
//真为奇数，假为偶数
visit[a]=true;
visit[b]=true;
//访问过标记为true
if(get(a)!=get(b))Union(a,b);
//如果不在一个集合就合并
}
for(int i=1;i<=n;i++){
if(dg[i])cnt[get(i)]++;
//统计每个点所在的图共有几个度数为奇数的
}
for(int i=1;i<=n;i++){
if(get(i)==i&&visit[i]){
//如果是根节点同时已经被访问过
if(cnt[i]>0)ans+=cnt[i]>>1;
//加上该图的答案
else ans++;
//否则该图可以一笔画，答案加1
}
}
cout<<ans;
return 0;
}