상근이의 여행

#include<iostream>
#include <queue>
#include <utility>
#include<cstring>
#include<cstdlib>

using namespace std;

int tc,n,m;
int map[1001][1001];
int d[1001][1001];
bool nation[1001];
int ans = 123456789;

bool check(){
    for(int i = 1; i <= n; i++){
        if(nation[i] == false)
            return false;
    }
    return true;
}

void bfs(int x, int y)
{
    queue<pair<int,int>> q;
    q.push({x,y});
    nation[x] = true;
    while(!q.empty()){
        x = q.front().first; y = q.front().second;
        q.pop();
        for(int i = 1; i <= n; i++){
            if(map[y][i] == 1 && d[y][i] == 0 && nation[i] == false){
                d[y][i] = d[x][y] + 1;
                nation[i] = true;
                q.push({y,i});
                break;
            }
        }
        if(ans > d[x][y]) return;
        if(q.empty()){
            ans = ans > d[x][y] ? d[x][y] : ans;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>tc;
    for(int t = 0; t< tc; t++){
        ans = 123456789;
        cin>>n>>m;
        int a,b;
        for(int i = 0; i < m; i++){
            cin>>a>>b;
            map[a][b] = 1;
            map[b][a] = 1;
        }
        /*for(int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cout << map[i][j] << " ";
            }
            cout << endl;
        }cout<<endl;*/

        /*for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(map[i][j] == 1){
                    d[i][j] = true;
                    bfs(i,j);
                    memset(d,0,sizeof(d));
                    memset(nation,false,sizeof(nation));
                    break;
                }
            }
        }*/
        cout<<n-1<<'\n';

    }
    return 0;
}

 

BFS로 풀면서 계속 시간초과가났던문제, 왜그런가 계속문제다시읽고 써보고하면서 느낀건..

그냥 모든곳을 다돌기위해선 무조건 n-1이여야한다는것이다...