글 읽기 - 어째서 시간 초과가 나는걸까요....ㅠㅠㅠ

specialjin1 8년 전 0

68%에서 시간초과가 납니다.. 몇주째 비슷한 아이디어로 막히고 있네요..

트리구조로 계속 쌓여나가는건데.. 어째서 재귀로 시간초과가 나는지 모르겠습니다으아...

아무리 멘탈 시뮬레이션을 해봐도 어떻게 해야 시간초과가 나는지 상상이 안가네요..

#include <iostream>
#include <vector>
using namespace std;
 
struct Edge {
    int A;
    int B;
    int C;
};
vector<pair<int,int>> *vertax;
struct Edge *edge;
int v,e;
bool check_flag=false;
 
void quicksort(Edge a[], int first, int end)
{   // edge들을 가중치 오름차순으로 정렬
    int i=first, j=end;
    Edge h;
    int x = a[(first+end)/2].C;
 
    do {
        while(a[i].C<x) i++;
        while(a[j].C>x) j--;
        if(i<=j) {
            h=a[i];
            a[i]=a[j];
            a[j]=h;
            i++;
            j--;
        }
    } while(i<=j);
    if(first<end) quicksort(a,first,j);
    if(i<end) quicksort(a,i,end);
}
int check_graph(int start,int now_edge, int pr_edge)
{    // 시작 노드와 현재 노드, 전 노드를 매개변수로
    int check_count=0,i;
    if((now_edge == start && pr_edge != start) || check_flag==true) {
        check_flag=true;    // 그래프일 경우 return 1
        return 1;
    }
    for(i=1;i<=vertax[now_edge].size();i++)
    {
        if(vertax[now_edge].at(i-1).first!=pr_edge)
        {    // 전 노드가 아닌 경우 연결해서 확인
            check_count += check_graph(start,vertax[now_edge].at(i-1).first,now_edge);
        }
    }
    return check_count;    // 그래프인 경우엔 1이상이 리턴됨
 
}
int kruskal()
{
    int i,j,weight=0;
    for(i=0;i<e;i++)
    {
        pair<int,int> con1,con2;
        con1.first = edge[i].B;
        con1.second = edge[i].C;
        con2.first = edge[i].A;
        con2.second = edge[i].C;
        vertax[edge[i].A].push_back(con1);
        vertax[edge[i].B].push_back(con2);
        if(check_graph(edge[i].A,edge[i].A,edge[i].A)>0)
        {
            vertax[edge[i].A].pop_back();
            vertax[edge[i].B].pop_back();
        }
        else {
            weight += edge[i].C;
        }
        check_flag = false;
    }
    return weight;
}
 
int main()
{
    int result;
    cin >> v >> e;
    vertax = new vector<pair<int,int>>[v+1];
    edge = new struct Edge[e];
    for(int i=0;i<e;i++)
    {
        cin >> edge[i].A >> edge[i].B >> edge[i].C;
    }
    quicksort(edge,0,e-1);
    result = kruskal();
    cout << result << endl;
    delete [] vertax;
    delete [] edge;
}

baekjoon 8년 전 2

check_graph를 union find를 사용하는 방법으로 바꿔보는 것은 어떨까요

specialjin1 8년 전 0

넵 찾아서 해결해보겠습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어째서 시간 초과가 나는걸까요....ㅠㅠㅠ

specialjin1 8년 전 0

baekjoon 8년 전 2

specialjin1 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말