Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.1 kB
4
Indexable
Never
#include <iostream>
using namespace std;

#define maxN 1001
#define inf 2147483647

int adj[maxN][maxN], doYeu[maxN], N, M, H, queue[maxN * maxN], nQ, topQ, maxYeu, dao;
bool inQ[maxN];

void BFS()
{
	int u = 0;
	while (topQ != nQ)
	{
		u = queue[topQ++]; inQ[u] = false; 

		for(int i = 1; i <= adj[u][0]; ++i)
			if(doYeu[adj[u][i]] > doYeu[u] + 1)
			{
				doYeu[adj[u][i]] = doYeu[u] + 1;
				if(!inQ[adj[u][i]]) queue[nQ++] = adj[u][i];
			}
	}
}


int main()
{
	ios::sync_with_stdio();
	freopen("input.txt", "r", stdin);

	int T, u, v; cin >> T;
	for(int tc = 1; tc <= T; ++tc)
	{
		cin >> N >> M >> H;

		for(int i = 0; i < N; ++i) adj[i][0] = 0, doYeu[i] = inf, inQ[i] = false;

		nQ = topQ = 0;
		for(int i = 0; i < M; ++i)
		{
			cin >> u;
			doYeu[u] = 0; queue[nQ++] = u; inQ[u] = true;
		}

		for(int i = 0; i < H; ++i)
		{
			cin >> u >> v;
			++adj[u][0]; adj[u][adj[u][0]] = v;
			++adj[v][0]; adj[v][adj[v][0]] = u;
		}

		BFS();

		maxYeu = -1;
		for(int i = 0; i < N; ++i)
			if(doYeu[i] > maxYeu) dao = i, maxYeu = doYeu[i];
		cout << dao << endl;
	}
	
	return 0;

pha hethong dien
#include <iostream>
using namespace std;

int n;
int res;

int queue[999999];
int front = 0, rear = 0;

int arr[105][105];
int visit[105][105];

void resetVisit(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			visit[i][j] = 0;
		}
	}
}

void noiDien(int city, int mangIndex[105], int id){
	for(int i = 0; i < id; i++){
		arr[city][mangIndex[i]] = 1;
		arr[mangIndex[i]][city] = 1;
	}
}

void loangVung(int x){
	front = 0, rear = 0;
	queue[rear++] = x;
	while(front < rear){
		int tp = queue[front++];
		for(int i = 1; i <= n; i++){
			if(visit[tp][i] == 0 && arr[tp][i] == 1){
				visit[tp][i] = 1;
				queue[rear++] = i;
			}
		}
	}
}

int demVung(int desCity){
	resetVisit();
	int vung = 0;
	for(int i = 1; i <= n; i++){
		if(i == desCity){
			continue;
		}
		bool vungMoi = true;
		bool vungLK = false;
		for(int j = 1; j <= n; j++){
			if(arr[i][j] == 1 && j != desCity) vungMoi = false;
			if(visit[i][j] == 0 && arr[i][j] == 1 && j != desCity){
				vungLK = true;
				visit[i][j] = 1;
				loangVung(j);
			}
		}
		if(vungMoi) vung++;
		if(vungLK) vung++;
	}
	return vung;
}

int phaDien(int city){
	int mangIndex[105], id = 0;
	//cat dien
	for(int i = 1; i <= n; i++){
		if(arr[city][i] == 1){
			mangIndex[id++] = i;
			arr[city][i] = 0;
			arr[i][city] = 0;
		}
	}
	int vung = demVung(city);
	noiDien(city, mangIndex, id); //noi dien
	return vung;
}

int main(){
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				cin >> arr[i][j];
			}
		}
		res = 0;
		int vungMax = 1;
		for(int i = 1; i <= n; i++){
			int vungBandau = demVung(0);
			int vungCatDien = phaDien(i);
			if(vungCatDien > vungMax && vungBandau != vungCatDien){
				vungMax = vungCatDien;
				res = i;
			}
		}

		cout << res << endl;
	}
	return 0;
}