Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
4
Indexable
Never
#include <iostream>
using namespace std;

int n,m;
int dem[25];
int cap[2][25];
int canh[25][25];
int visit[25][25];
int Q[100000];
int Q1[100000];
int Qd[100000];
int f = -1;
int kq;

void push(int x,int y, int d){
	f++;
	Q[f] = x;
	Q1[f] = y;
	Qd[f] = d;
}
void pop(int &x,int &y, int &d){
	x = Q[f];
	d = Qd[f];
	y = Q1[f];
	f--;
}
void re_canh(){
	for(int i = 0; i < n; i++){
		for(int j = 0 ; j < n; j++){
			canh[i][j] = 0;
		}
	}
}
void re_visit(){
	for(int i = 0; i < n; i++){
		for(int j = 0 ; j < n; j++){
			visit[i][j] = 0;
		}
	}
}

void DFS(int x, int y, int d){
	re_visit();
	f = -1;
	push(x,y,d);
	visit[x][y] = visit[y][x] = 1;
	while(f > -1 ){
		pop(x,y,d);
		if(d > kq) kq = d;
		visit[x][y] = visit[y][x] = 1;
		for(int i = 0; i < n; i++){
			if(canh[y][i] == 1 && visit[y][i] == 0){
				push(y,i,d+1);
				//visit[x][i] = visit[i][x] = 1 ;
				if(d + 1 > kq) kq = d + 1;

			}
		}
	}
}
int main(){
	freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n >> m;
		re_canh();
		for(int i = 0; i < m; i++){
			int x, y;
			cin >> x >> y;
			cap[0][i] = x;
			cap[1][i] = y;
			canh[x][y] = canh[y][x] = 1;
		}
		kq = 0;
		for(int i = 0; i < m; i++){
			DFS(cap[0][i],cap[1][i],1);
			DFS(cap[1][i],cap[0][i],1);
		}
		cout <<"#" << tc << " " <<  kq << endl;
	}
	return 0;
}