UVa – 924 – Spreading the News

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>

#define SET(a, v) for(unsigned int ZZ =0; ZZ < (sizeof(a)/sizeof(int)); ZZ++)(a[ZZ]) = (v);
#define PRINT(a)  for(unsigned int ZZ =0; ZZ < (sizeof(a)/sizeof(int)); ZZ++) printf("%d -", (a[ZZ]));
#define INF 1<<29

using namespace std;
#define MAX 40

int main() {

	int N, M, E, u, v, i, j, source, maxI;
	cin >> N;
	bool graph[N][N], connected[N];
	for(int i=0; i<N; i++)
		memset(graph[i], 0, sizeof graph[i]);
	memset(connected, 0, sizeof connected);
	int d[N], freq[N];

	for (i = 0; i < N; i++) {
		cin >> M;
		while (M--) {
			cin >> j;
			graph[i][j]  = true;
			connected[i] = true;
		}
	}

	cin >> E;
	while (E--) {
		queue<int> que;
		cin >> source;

		for(i=0; i<N; i++)	d[i] = -INF;
		memset(freq, 0, sizeof freq);
		d = 0;	que.push(source);

		while(!que.empty()){
			u = que.front();	que.pop();
			for(v=0; v<N; v++)
				if(graph[u][v] && d[v]==-INF){
					que.push(v);
					freq[(d[v]=d[u]+1)]++;
				}
		}

		for(i=1, maxI=1; i<N; i++)
			maxI = freq[maxI] < freq[i] ? i : maxI;

		if(!connected)
			cout<< "0" << endl;
		else
			cout << freq[maxI] << " " << maxI << endl;
	}

	return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: