原始生物 题解

原始生物

分析

一句话题意：

给定一张图，将其扩展成欧拉回路。
如果是欧拉回路，那么就应该在边上再加一
否则直接加上入度和出度间的较大者。
end。。。

判环

void dfs(int x, int root) {
	vis[x] = 1;//标记
	if (in[x] != out[x]) {
		c[root] = 0;
	}
	for (int i = 0; i < G[x].size(); i++) {
		if (vis[G[x][i]] == 0)
			dfs(G[x][i], root);	
	}
}

代码

#include <vector>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 50005;

int n, m, ans, sum, num[MAXN], in[MAXN], out[MAXN];
bool vis[MAXN], flag, is[MAXN];
bool c[MAXN];
vector<int> G[MAXN];

void dfs(int x, int root) {
    vis[x] = 1;
    if (in[x] != out[x]) {
        c[root] = 0;
    }
    for (int i = 0; i < G[x].size(); i++) {
        if (vis[G[x][i]] == 0)
            dfs(G[x][i], root);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
        is[u] = 1;
        is[v] = 1;
        in[v]++;
        out[u]++;
        m = max(u, max(m, v));
    }
    for (int i = 1; i <= m; i++) {
        if (!vis[i] && is[i]) {
            c[i] = 1;
            dfs(i, i);
        }
    }
    for (int i = 1; i <= m; i++) {
        if (is[i])
            ans += max(in[i], out[i]);
    }
    for (int i = 1; i <= m; i++) {
        if (c[i] == 1) {
            ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}