Codeforces 27D（二分染色）

要点

将边作为染色，如果交叉则异色

#include <cstdio>

#include <algorithm>

#include <functional>

using namespace std;

int n, m;

int a[101], b[101], c[101];

int main() {

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++) {

		scanf("%d %d", &a[i], &b[i]);

		if (a[i] > b[i])

			swap(a[i], b[i]);

		c[i] = -1;

	}

	function<void(int, int)> dfs = [&](int u, int color) {

		if (c[u] != -1 && c[u] != color) {

			puts("Impossible"); exit(0);

		} else if (c[u] == -1) {

			c[u] = color;

			for (int i = 1; i <= m; i++) {

				if (a[i] < a[u] && b[i] > a[u] && b[i] < b[u])

					dfs(i, color ^ 1);

				if (a[i] > a[u] && a[i] < b[u] && b[i] > b[u])

					dfs(i, color ^ 1);

			}

		}

	};

	for (int i = 1; i <= m; i++)

		if (c[i] < 0)

			dfs(i, 0);

	for (int i = 1; i <= m; i++)

		putchar(c[i] ? 'i' : 'o');

}

巴特西

Codeforces 27D（二分染色）

要点

最新文章

热门文章