Untitled
unknown
plain_text
a year ago
1.6 kB
3
Indexable
Never
//The Settlers of Catan #define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; int n , m, front, rear; int arr[30][30], vs[30][30], d[30][30], queue_i[9000000], kc[30]; void set(){ for(int i = 0; i < n; i++){ kc[i] = 0; for(int j = 0; j < n; j++){ vs[i][j] = 0; } } } void Push(int x){ queue_i[rear] = x; rear++; } void bfs(int x){ kc[x] = 1; front = 0; rear = 0; Push(x); while(rear != front){ int y = queue_i[front]; front++; for(int i = 1; i <= d[y][0]; i++){ if(vs[y][d[y][i]] == 0){ if(!kc[d[y][i]]){ kc[d[y][i]] = kc[y] + 1; vs[y][d[y][i]] = 1; vs[d[y][i]][y] = 1; Push(d[y][i]); } else if(kc[d[y][i]] < kc[y] + 1){ kc[d[y][i]] = kc[y] + 1; vs[y][d[y][i]] = 1; vs[d[y][i]][y] = 1; Push(d[y][i]); } } } } } int main(){ freopen("ip.txt", "r", stdin); int T; cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> n >> m; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ arr[i][j] = 0; d[i][j] = 0; } } for(int i = 1; i <= m ; i++){ int x, y; cin >> x >> y; arr[x][y] = 1; arr[y][x] = 1; } for(int i = 0; i < n; i++){ int cnt = 1; for(int j = 0; j < n; j++){ if(arr[i][j]==1){ d[i][cnt] = j; cnt++; } } d[i][0] = cnt-1; } int res = 0; for(int i = 0; i < n; i++){ set(); bfs(i); for(int i = 0; i < n; i++){ //cout << kc[i] <<endl; res = max(res, kc[i]); } } cout << res << endl; } return 0; }