http://main.edu.pl/en/archive/oi/19/tou 19th Polish Olympiad in Informatics Stage II - day 0

Tour de Byteotia.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 1001000;
const int maxm = 2002000;

int n, m, k;
int par[maxn];

struct Edge {
	int u, v;
	bool ok;
	Edge() {}
	Edge(int uu, int vv, bool o) {
		u = uu; v = vv; ok = o;
	}
};
Edge e[maxm];

int find(int x) {
	if (par[x] != x)
		par[x] = find(par[x]);
	return par[x];
}

void init() {
	for (int i = 0; i < maxn; i++)
		par[i] = i;
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		e[i] = Edge(u, v, false);
		if (u > k && v > k)
			par[find(u)] = find(v);
	}
}

void work() {
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		if (e[i].u <= k || e[i].v <= k) {
			if (find(e[i].u) == find(e[i].v)) {
				e[i].ok = true; ans++;
			} else {
				par[find(e[i].u)] = find(e[i].v);
			}
		}
	}
	printf("%d\n", ans);
	for (int i = 1; i <= m; i++) {
		if (e[i].ok == true) {
			int a = min(e[i].u, e[i].v);
			int b = max(e[i].u, e[i].v);
			printf("%d %d\n", a, b);
		}
	}
}

int main() {
	init();
	work();
	return 0;
}