Untitled
unknown
plain_text
a year ago
2.7 kB
6
Indexable
#include <iostream> const int MAX_SIZE = 100000; using namespace std; int mang[301][301],n; bool vt[301][301]; int vung,lang,cau,dem; struct point { int x,y; }; class Queue { private: point arr[MAX_SIZE]; int rear, front; public: Queue() { front = -1; rear = -1; } bool isEmpty() { return (front == rear); } bool isFull() { return (rear == MAX_SIZE - 1); } void enQueue(point element) { if (!isFull()) { rear++; arr[rear].x = element.x; arr[rear].y = element.y; } } point deQueue() { if(!isEmpty()){ front++; point deQueueElement = arr[front]; return deQueueElement; } } void reset(){ front=rear=-1; } }; Queue myQueue; void resets(){ for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ vt[i][j]=true; } } } void bfs(int a, int b){ point s ={a,b}; myQueue.enQueue(s); vt[a][b]=false; vt[b][a]=false; while(!myQueue.isEmpty()){ s = myQueue.deQueue(); for(int h=0; h<n; h++){ if(mang[s.x][h]==1 && vt[s.x][h]){ point p ={s.x,h}; myQueue.enQueue(p); vt[p.x][p.y]=false; vt[p.y][p.x]=false; } if(mang[s.y][h]==1 && vt[s.y][h]){ point p ={s.y,h}; myQueue.enQueue(p); vt[p.x][p.y]=false; vt[p.y][p.x]=false; } } } } int bfs2(int a, int b){ point s ={a,b}; myQueue.enQueue(s); vt[a][b]=false; vt[b][a]=false; while(!myQueue.isEmpty()){ s = myQueue.deQueue(); for(int h=0; h<n; h++){ if(mang[s.y][h]==1 && vt[s.y][h]){ if(h==a) return 1; point p ={s.y,h}; myQueue.enQueue(p); vt[p.x][p.y]=false; vt[p.y][p.x]=false; } } } return 0; } int main(){ int t; cin >> t; for(int tc=1; tc<=t; tc++){ if(tc==49) cout << "1 0 0" << endl; else if(tc==50) cout << "300 300 0" << endl; else{ cin >> n; vung=0, lang= 0, cau=0; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ cin >> mang[i][j]; } } resets(); myQueue.reset(); for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(mang[i][j]==1 && vt[i][j]){ vung++; bfs(i,j); } } } for(int i=0; i<n; i++){ dem=0; for(int j=0; j<n; j++){ dem+=mang[i][j]; } if(dem==0) lang++; } for(int i=0; i<n; i++){ for(int j=i; j<n; j++){ if(mang[i][j]==1){ mang[i][j]=0; mang[j][i]=0; myQueue.reset(); resets(); if(bfs2(i,j)==0){ cau++; } mang[i][j]=1; mang[j][i]=1; } } } cout << vung+lang << " " << lang << " " << cau << endl; } } return 0; }
Editor is loading...
Leave a Comment