4-K Tree판별문제 코드리뷰 부탁드리겠습니다.

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

#include<bits/stdc++.h>

using namespace std;

int t,n,m, visited[1004];
vector<int> a[1004];


int solve(int before, int here){
    int ret = 1;
    visited[here]=1;
    for(int there: a[here]){
        if(there==before) continue;
        if(visited[there]) return -1000;

        ret += solve(here, there);
    };
    return ret;

}

int main(){
    cin>>t;
    while(t--){
        fill(visited,visited+1004,0);
        for(int i=0; i<1004; i++){
            a[i].clear();
        }
        cin>>n>>m;
        for(int i=0; i<m; i++){
            int temp1=0,temp2=0;
            cin>>temp1>>temp2;
            a[temp1].push_back(temp2);
            a[temp2].push_back(temp1);
        }

        if(n==solve(0,1)) cout<<"tree"<<'\n';
        else cout<<"graph"<<'\n';
    }

    return 0;
}

저는 dfs를 돌때 현재노드와 다음노드를 같이 넘겨서, 부모노드를 판별할 수 있게끔 했고, 부모노드가 아닌걸 재방문하면, 싸이클로 판별해서 쓰레기값이 들어가도록 코드를 짰습니다.

근데 큰돌님 코드는 0ms인데 제 코드는 4ms더라구요.. 어디에서 차이가 나는걸까요?ㅠㅠ

답변 1

0

큰돌

2025-09-22T02:56:37.454Z

안녕하세요 ㅎㅎ

제 코드와 큰 차이가 없습니다.

잘 짜셨네요 ㅎㅎ

사실 0 ~ 4ms 차이는 ios ... 이부분만 최적화하시면 더 빨라집니다.

다음 부분을 추가해보시겠어요?

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>t;
    while(t--){

수강생님 코드가 0ms 된 모습.

 

감사하니다.