FZU 2112 Tickets (连通分量&欧拉通路)

http://acm.fzu.edu.cn/problem.php?pid=2112

第一种思路：

首先计算图的连通分量个数c，没提到的点就不统计了。

然后对每个连通分量单独讨论，要使其有欧拉通路，则图中至多有2个度为奇数的点。
所以每多出2个度为奇数的点，我们就用一条线连起来（也就是多买一张票）。
（注意，因为单个连通分量的所有点的度数之和为偶数，所以不可能存在奇数个奇数度数的点）

最后答案=(c-1)+各个连通分量的max(0,(奇度数点个数-2)/2)

PS：不判连通分量也能过，这数据也太弱了吧。。

第二种思路：

使用并查集即可，不需要建图，比dfs快很多且省内存。

代码1：

/*796ms,4676KB*/

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int mx = 100005;

vector<int> v[mx];
int deg[mx];///点的度
int cnt;
bool vis[mx];

void dfs(int i)
{
	if (vis[i]) return;
	cnt += deg[i] & 1;
	vis[i] = true;
	for (int j = 0; j < v[i].size(); ++j)
		dfs(v[i][j]);
}

int main()
{
	int T, n, m, a, b, i, allcnt;
	scanf("%d", &T);
	while (T--)
	{
		memset(deg, 0, sizeof(deg));
		scanf("%d%d", &n, &m);
		for (i = 1; i <= n; ++i) v[i].clear();
		while (m--)
		{
			scanf("%d%d", &a, &b);
			v[a].push_back(b);
			v[b].push_back(a);
			++deg[a], ++deg[b];
		}
		allcnt = -1;
		memset(vis, 0, sizeof(vis));
		for (i = 1; i <= n; ++i)
			if (!vis[i] && deg[i])
			{
				cnt = 0, dfs(i);
				++allcnt;
				cnt = (cnt - 2) >> 1;
				if (cnt < 0) cnt = 0;
				allcnt += cnt;
			}
		printf("%d\n", allcnt);
	}
	return 0;
}

代码2：

/*531ms,1576KB*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx = 100005;

int fa[mx], rk[mx], cnt[mx];
bool odd[mx], has[mx];

int find(int x) {return ~fa[x] ? fa[x] = find(fa[x]) : x;}

void merge(int x, int y)
{
	x = find(x), y = find(y);
	if (x == y) return; ///已合并
	if (rk[x] < rk[y])
		fa[x] = y;
	else
	{
		fa[y] = x;
		if (rk[x] == rk[y]) ++rk[x];
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	int t, n, m, a, b, i, ans;
	scanf("%d", &t);
	while (t--)
	{
		memset(fa, -1, sizeof(fa));
		memset(rk, 0, sizeof(rk));
		memset(odd, 0, sizeof(odd));
		memset(has, 0, sizeof(has));
		scanf("%d%d", &n, &m);
		while (m--)
		{
			scanf("%d%d", &a, &b);
			odd[a] = !odd[a], odd[b] = !odd[b];
			has[a] = has[b] = true;
			merge(a, b);
		}
		memset(cnt, 0, sizeof(cnt));
		for (i = 1; i <= n; ++i)
			if (odd[i]) ++cnt[find(i)]; /// 统计每个连通分量的奇度数点个数
		memset(odd, 0, sizeof(odd)); /// 改变意义:下面odd当vis使用
		ans = -1;
		for (i = 1; i <= n; ++i)
		{
			a = find(i);
			if (has[a] && !odd[a])
			{
				ans += max(1, cnt[a] >> 1);
				odd[a] = true;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

FZU 2112 Tickets (连通分量&欧拉通路),布布扣,bubuko.com

FZU 2112 Tickets (连通分量&欧拉通路)

原文：http://blog.csdn.net/synapse7/article/details/20309171