1. C++, Tobias Fuchs


/*
* Author: Tobias Fuchs
* Problem: 336
* Verdict: Accepted
* Runtime: 0.910
*/

#include<stdio.h>
#include<vector>
#include<map>
#include<iostream>
#include<utility>
#include<string.h>

#ifdef _NOLOG
#define log(msg) ::std::cout << msg << ::std::endl;
#else
#define log(msg) (void*)(0)
#endif

typedef struct {
int number;
::std::vector<unsigned int> connections;
} vertex_t;
typedef vertex_t * vertex_p;

// Nodes that could be reached
::std::map<unsigned int, unsigned int> reached_nodes;
// Nodes that could be reached with TTL=0
::std::vector<unsigned int> end_nodes;
// Nodes that could not be reached
::std::vector<unsigned int> unreachable_nodes;
// Connection map: id -> vertex(id, connections(id[])
::std::map<unsigned int, vertex_t> pool;

typedef ::std::pair<unsigned int, vertex_t> Pool_Entry;
typedef ::std::pair<unsigned int, unsigned int> Reached_Entry;

inline void create_node(unsigned int id) {
vertex_t vertex;
vertex.number = id;
pool.insert(Pool_Entry(id, vertex));
reached_nodes.insert(Reached_Entry(id, (unsigned int)0));
}

inline void add_connection(unsigned int id_a, unsigned int id_b)
{
if(pool.find(id_a) == pool.end()) { create_node(id_a); }
if(pool.find(id_b) == pool.end()) { create_node(id_b); }
pool[id_a].connections.push_back(id_b);
pool[id_b].connections.push_back(id_a);
}

inline void delete_end_node(unsigned int vid) {
::std::vector<unsigned int>::iterator pos = find(end_nodes.begin(), end_nodes.end(), vid);
if(pos != end_nodes.end()) {
end_nodes.erase(pos);
}
}

// Delete duplicate vector elements magic
inline void unique_vector(::std::vector<unsigned int> & v) {
::std::sort(v.begin(), v.end());
::std::vector<unsigned int>::iterator new_end_pos;
new_end_pos = ::std::unique(v.begin(), v.end());
v.erase(new_end_pos, v.end());
}

void bfs_mark(unsigned int start) {
vertex_t v = pool[start];
::std::vector<unsigned int> connections = v.connections;
::std::vector<unsigned int>::iterator it = connections.begin();
// Mark current node as reached ...
reached_nodes[start] = 1; // ttl > 0 --> reached
// For every node within reach of current node ...
for(; it != connections.end(); ++it) {
// If node has not been reached before ...
if(find(unreachable_nodes.begin(), unreachable_nodes.end(), (*it)) == unreachable_nodes.end() &&
reached_nodes[*it] == 0) {
// add it to list of unreachable nodes:
unreachable_nodes.push_back(*it);
bfs_mark(*it);
}
}
}

void bfs_mark() {
::std::vector<unsigned int>::iterator it = end_nodes.begin();
for(; it != end_nodes.end(); ++it) {
bfs_mark(*it);
}
}

void bfs(unsigned int start, unsigned int ttl) {
vertex_t v = pool[start];
::std::vector<unsigned int> connections = v.connections;

reached_nodes[start] = ttl;
// TTL = 0: mark as end node and cancel this branch
if(ttl <= 1) { end_nodes.push_back(start); return; }
// TTL > 0: remove node from end nodes, in case it has been reached with TTL 0 before:
else { delete_end_node(start); }

::std::vector<unsigned int>::iterator it = connections.begin();
for(; it != connections.end(); ++it) {
// Recurse unless node has been reached before with better TTL:
if(reached_nodes[*it]+1 < ttl) {
bfs(*it, ttl-1);
}
}
}

int main(int argc, char * argv[])
{

int n_connections, k, i, m, n, ttl, start, n_case, n_separated;
n_case = 0;
while(scanf("%d",&n_connections) && n_connections)
{
k = 0;
for(i = 0; i<n_connections; i ++)
{
scanf("%d%d",&m,&n); // read single connection
add_connection(m,n);
}
while(scanf("%d%d",&start,&ttl) == 2) { // read queries
if(ttl == 0 && start == 0) break;

bfs(start, ttl+1);
// unique_vector(end_nodes);
bfs_mark();

// Also add nodes from separated graph:
n_separated = 0;
::std::map<unsigned int, vertex_t>::iterator sep = pool.begin();
for(; sep != pool.end(); ++sep) {
if(reached_nodes[sep->first] == 0) ++n_separated;
}
::std::cout << "Case " << ++n_case << ": " << n_separated + unreachable_nodes.size() << " nodes not reachable from node " << start << " with TTL = " << ttl << "." << ::std::endl;

// Reset for next query:
reached_nodes.clear();
unreachable_nodes.clear();
end_nodes.clear();
}
// Reset for next network:
pool.clear();
}
return 0;
}