Untitled
unknown
plain_text
a year ago
2.1 kB
3
Indexable
Never
#include<iostream> using namespace std; int const max_len= 305; int map[max_len][max_len]; // Map dau vao int visit[max_len]; // danh dau dinh int visitEdge[max_len][max_len]; // danh dau cac canh int n; void Try(int u){ for(int i=0; i<n;i++){ if(map[u][i]==1 && !visit[i]){ visit[i]=1; Try(i); } } } int getRount(){ // tra ve so vung trong map int ans=0; for(int i=0; i<n;i++){ if( !visit[i]){ // dinh i chua dc xet ans++; Try(i); } } return ans; } void reset(){ for(int i=0; i<n;i++){ visit[i]=0; // reset mangvisit } } bool flag2; void checkBrigde(int d1,int d2){ for(int i=0; i<n;i++){ if(map[d1][i]==1 && !visit[i]){ if(i==d2){ //neu ma tu d1 van di dc den d2 flag2=false; return; } visit[i]=1; checkBrigde(i,d2); if(!flag2) return ; } } } int getBridge(){ int ans=0; for(int i=0; i<n;i++){ for(int j=0;j<n;j++){ visitEdge[i][j]=0; // reset mangvisit } } for(int r=0; r<n;r++) { for(int c=0; c<n;c++){ if( map[r][c]==1 && visitEdge[r][c]==0){ map[r][c]=map[c][r]=0 ; // thu bo duong di tu r den c visitEdge[r][c]=visitEdge[c][r]=1; flag2=true; reset(); checkBrigde(r,c); if(flag2) ans++; map[r][c]=map[c][r]=1; } } } return ans; } int main() { int test_case; int T; int Answer; int cntAlone; int cntEdge; //freopen("text.txt", "r", stdin); cin >> T; for(test_case = 1; test_case <= T; ++test_case) { cin>>n; cntAlone=0; cntEdge=0; for(int i=0; i<n;i++){ bool flag=true; // danh dau vung cco lap for(int j=0; j<n;j++){ cin>>map[i][j]; if(map[i][j]==1){ cntEdge++; flag=false; } } if(flag) cntAlone++; } cntEdge=cntEdge/2; reset(); int group = getRount(); int cntBridge=0; if((n>2 && cntEdge == (n*(n-1)/2)) || cntEdge==0) cntBridge=0; else { cntBridge=getBridge(); } cout << group << " " << cntAlone<<" "<<cntBridge << endl; } return 0; }