Untitled

 avatar
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