UVA – 280 – Vertex

  • Problem Statement : UVA – 280 – Vertex
  • Type : Graphs, Floyd-Warshall
  • Optimization : This is a connectivity problem but the multi-source input makes it better to solve it using Floyd’s
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string.h>
#include <stdio.h>
using namespace std;
#define S(ZZ) (ZZ)*(ZZ)
#define FOR(ii, i0, in) for((ii)=(i0); (ii)<(in); (ii)++)
#define FOR2d(ii, jj, i0, j0, in, jn) FOR(ii, i0, in) FOR(jj, j0, jn)
#define FOR3d(kk, ii, jj, k0, i0, j0, kn, in, jn) FOR(kk, k0, kn) FOR(ii, i0, in) FOR(jj, j0, jn)
#define MAXN 102
#define INF 999999999L
typedef pair<int, int> Point;

int main() {
	int t = 1, n, N, E, x1, y1, i, j, k;
	while ((cin >> N) && (n = N)) {
		double g[MAXN][MAXN];
		FOR2d(i, j, 0, 0, MAXN, MAXN)	g[i][j] = INF;
		while ((cin >> i) && i) while ((cin >> j) && j) g[i][j] = 1;
		// Floyd-Warshall DP
		FOR3d(k, i, j, 1, 1, 1, N+1, N+1, N+1)
			g[i][j] = min(g[i][j], max(g[i][k], g[k][j]));

		cin >> t;
		while (t--) {
			cin >> i;
			vector<int> ans;
			FOR(j, 1, N+1) if (g[i][j] == INF)	ans.push_back(j);
			cout << ans.size();
			FOR(j, 0, ans.size()) cout << " " << ans[j];
			cout << endl;
		}
	}
	return 0;
}
Advertisements

2 thoughts on “UVA – 280 – Vertex

  1. Purificadoras de agua says:

    I’m surely as a consequence glad to check out this. Is actually the shape of pdf to be taking into account in no way a random falsehoods which may be toward the some a blog. Comprehend you are spreading this method best doctor.

  2. Thanks a lot Sir, Glad you liked it.. I hope it would not be taken into consideration as I’m just a beginner 🙂

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: