You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
bapc-prelim-2015/bapc-b.cpp

65 lines
1.3 KiB

#include <iostream>
#include <cstring>
#include <list>
#include <vector>
typedef std::vector< std::vector<bool> > Graph;
int recurse(Graph &graph, bool* todo, int j, int N, std::vector<int> &members) {
if (!todo[j]) return 0;
todo[j] = false;
members.push_back(j);
int total = 1;
for (int k = 0; k < N; k++) {
if (graph[j][k]) {
total += recurse(graph, todo, k, N, members);
}
}
return total;
}
int main(int argc, char const *argv[])
{
int C;
std::cin >> C;
for (int i = 0; i < C; ++i)
{
int N, M;
std::cin >> N;
std::cin >> M;
N *= 2;
Graph graph(N, std::vector<bool>(N));
for (int j = 0; j < N; j++) {
for(int k = 0; k < N; k++) {
graph[j][k] = (j != k);
}
}
for (int j = 0; j < M; j++) {
int A, B;
std::cin >> A;
std::cin >> B;
A--; B--;
if (A == N || B == N) {
std::cerr << "too high" << std::endl;
}
graph[A][B] = false;
graph[B][A] = false;
}
std::list<int> groups;
std::list< std::vector<int> > group_members;
int temp = N;
bool todo[N];
for(int j = 0; j < N; j++) {
if (!todo[j]) continue;
group_members.emplace_back(std::vector<int>());
groups.push_back(recurse(graph, todo, j, N, group_members.back()));
}
for (int c : groups) {
std::cout << "group: " << c << std::endl;
}
/* code */
}
return 0;
}