题解【CF209C Trails and Glades】

CF209C Trails and Glades
解题报告

图论基础题。

考虑一张无向联通图存在欧拉回路的条件是什么：

每一个点的度数均为偶数。

但这个条件的前提是连通图，那么我们可以考虑每一个连通块。

若这个连通块所有点度数均为偶数，那么我们可以从这个连通块往外连两条边，与其它连通块合并，贡献为 \(1\)。

若有 \(k\) 个点的度数是奇数，那么我们只保留两个这样奇数点来往外连边即可，其余点相互连，贡献是 \(\frac{k}{2}+1\)。

注意贡献为 \(1\) 的意思是，原本是要连两条边的，但由于两个连通块的相互连的话，每一条边会被算两次，所以连两条边只算一条边的贡献。

注意坑点：

若一个连通块只有一个点这个连通块是不用考虑的，但如果有自环是需要考虑的。

代码：

const int MAXN(1e6+10);

int n,m;
struct E{int to,nxt;};
E edge[MAXN<<1];

int head[MAXN],tot;

inline void add_edge(int u,int v)
{
	edge[++tot].nxt=head[u];
	head[u]=tot;
	edge[tot].to=v;
	return;
}

int cnt,deg[MAXN];
bool vis[MAXN];
vector<int>G[MAXN];

inline void dfs(int u)
{
	vis[u]=true;
	G[cnt].push_back(u);
	gra(i,u)
	{
		int v=edge[i].to;
		if(!vis[v]) dfs(v);
	}
	return;
}

int ans;

inline int Count(int i)
{
	int num=0;
	rep(j,0,(int)G[i].size()-1) if(deg[G[i][j]]&1) ++num;
	return num;
}

int main()
{
    n=read(),m=read();
    while(m--)
    {
    	int u=read(),v=read();
    	add_edge(u,v),add_edge(v,u);
    	++deg[u],++deg[v];
    }
    rep(i,1,n) if(!vis[i])
    {
    	++cnt;
    	dfs(i);
    	if(G[cnt].size()==1&&G[cnt][0]!=1&&deg[i]==0) G[cnt--].pop_back();
    }
    if(cnt==1)
    {
    	printf("%d\n",Count(1)>>1);
    	return 0;
    }
    rep(i,1,cnt)
    {
    	int num=Count(i);
    	if(!num) ++ans;
    	else ans=ans+(num>>1);
    }
    printf("%d\n",ans);
    return 0;
}