Untitled
unknown
plain_text
24 days ago
2.7 kB
1
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; #define MAXSIZE 305 #define MAXQUEUE 100000 class Queue { int head, rear; int A[MAXQUEUE]; public: Queue(); ~Queue(); void enQueue(int inS); int deQueue(); bool is_Empty(); bool is_Full(); void reset(); private: }; Queue::Queue() { head = rear = -1; } Queue::~Queue() { } void Queue::enQueue(int inS) { A[++rear] = inS; } int Queue::deQueue() { return A[++head]; } bool Queue::is_Empty() { if (head == rear) return true; return false; } bool Queue::is_Full() { if (rear == MAXQUEUE - 1) return true; return false; } void Queue::reset() { head = rear = -1; } Queue mQueue; int nTestcase, N, isoVillage, isoVillageF, region, village, bridge; int Map[MAXSIZE][MAXSIZE]; bool visited[MAXSIZE]; int countWay[MAXSIZE]; bool res; bool check(int start, int end) { bool result = false; for (int i = 1; i <= N; i++) { visited[i] = false; } mQueue.reset(); mQueue.enQueue(start); visited[start] = true; while (mQueue.is_Empty() == false && result == false) { village = mQueue.deQueue(); for (int j = 1; j <= N; j++) { if (j == end && Map[village][j] != 0) { result = true; break; } if (Map[village][j] != 0 && visited[j] == false) { mQueue.enQueue(j); visited[j] = true; } } } return result; } int main() { freopen("input.txt", "r", stdin); cin >> nTestcase; for (int testcase = 1; testcase <= nTestcase; testcase++) { cin >> N; isoVillageF = 0; for (int i = 1; i <= N; i++) { countWay[i] = 0; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { cin >> Map[i][j]; if (Map[i][j] == 1) countWay[i]++; } visited[i] = false; } //iso Village for (int i = 1; i <= N; i++) { if (countWay[i] == 0) isoVillageF++; } //Region region = 0; mQueue.reset(); for (int i = 1; i <= N; i++) { if (visited[i] == false) { region++; mQueue.enQueue(i); visited[i] = true; while (mQueue.is_Empty() == false) { village = mQueue.deQueue(); for (int j = 1; j <= N; j++) { if (Map[village][j] == 1 && visited[j] == false) { mQueue.enQueue(j); visited[j] = true; } } } } } //Bridge bridge = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (Map[i][j] == 1) { Map[i][j] = Map[j][i] = 0; res = check(i, j); if (!res) bridge++; Map[i][j] = Map[j][i] = 2; } } } cout << region << " " << isoVillageF << " " << bridge << endl; } return 0; }