Untitled
unknown
c_cpp
a year ago
1.7 kB
6
Indexable
#include<iostream> using namespace std; int T,n,a[1001][1001]; int visited[1001]; int component; int maxx; int used[1001]; int res; struct Stack { int stack[10001]; int top; Stack(){ reset(); } void reset(){ top=-1; } void push(int value){ stack[++top]=value; } int pop(){ return stack[top--]; } bool isEmpty(){ return top==-1; } }; void reset(){ for (int i=0 ;i<n;i++){ visited[i]=0; } } void resetUsed(){ for (int i=0 ;i<n;i++){ used[i]=0; } } void dfs(int x){ Stack s; s.push(x); while(!s.isEmpty()){ int u=s.pop(); if(!visited[u]){ visited[u]=1; for (int i=0 ;i<n;i++){ if(a[u][i]==1&&!visited[i]){ s.push(i); } } } } } void dfs2(int x){ Stack s; s.push(x); while(!s.isEmpty()){ int u=s.pop(); if(!used[u]){ used[u]=1; for (int i=0 ;i<n;i++){ if(a[u][i]==1&&!used[i]){ s.push(i); } } } } } void demtplt(int x){ int dem=0; used[x]=1; for (int i=0 ;i< n;i++){ if(!used[i]){ dem++; dfs2(i); } } //cout<<"tplt :"<<dem<<endl; int value=dem-1; if(dem>res){ res=dem; } } int main(){ freopen("input.txt","r",stdin); cin>>T; for (int t=1 ;t<=T;t++){ component=0; maxx=0; res=0; cin>>n; reset(); for (int i=0 ;i<n;i++){ for (int j=0 ;j<n;j++){ cin>>a[i][j]; } } for (int i=0 ;i<n;i++){ if(!visited[i]){ dfs(i); component++; } } for (int i=0 ;i<n;i++){ resetUsed(); demtplt(i); } if(res==1) cout<< 0<<endl; else cout<<res<<endl; //cout<<component<<endl; } return 0; }
Editor is loading...
Leave a Comment