Nguyen+Duc+Anh.cpp

mail@pastecode.io avatar
unknown
c_cpp
15 days ago
1.1 kB
1
Indexable
Never

#include <iostream>

using namespace std;
#define K 1000
int Answer, N, M, H, T;
int E[K][K];
int O[K];
int Q[K+1];
int check[K];
void input()
{
	cin >> N >> M >> H;
	int x, y;
	for(int i = 0; i < N; i++)
	{
		O[i] = K+1;
		check[i] = 0;
		for(int j = 0; j < N; j++)
			E[i][j] = 0;
	}
	for(int i = 0; i < M; i++)
	{
		cin >> x;
		O[x] = 0;
	}
	for(int i = 0; i < H; i++) {
		cin >> x >> y;
		E[x][y] = 1;
	}
}

void bfs(int v)
{
	int tail = 0;
	Q[tail] = v;
	int head = 0;

	while(head <= tail)
	{
		v = Q[head++];
		for(int i = 0; i < N; i++)
		{
			if((E[v][i] == 1 || E[i][v] == 1) && O[v] + 1 < O[i])
			{
				Q[++tail] = i;
				O[i] = O[v] + 1;
			}
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	//freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 0; test_case  < T; test_case++)
	{
		input();
		Answer = 0;
		for(int i = 0; i < N; i++)
			if(O[i] == 0)
				bfs(i);
		int max = O[0];
		for(int i = 0; i < N; i++)
		{
			if(O[i] > max)
			{
				max = O[i];
				Answer = i; 
			}
		}
		cout << Answer << endl;
	}

	return 0;
}
Leave a Comment