FZU 2112 Tickets (连通分量&欧拉通路)
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
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;
}| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |