글 읽기 - 시간초과가 납니다

myju742 5년 전 0

코사라주 알고리즘으로 구현했고 예제는 맞게 돌아가는데 시간초과가 납니다. 어디서 잘못된걸까요?

#include <bits/stdc++.h>
using namespace std;

#define MAX_V   10007
#define MAX_E   100007

bool fvisited[MAX_V], bvisited[MAX_V];
int counter, num_sccs, V, E;
vector<vector<int> > scc;
vector<int> adj[MAX_V], rev[MAX_V];
pair<int, int> f[MAX_V];


void DFS_forward(int u){
    fvisited[u]=true;
    for(int v:adj[u]){
        if(!fvisited[v]){
            DFS_forward(v);
        }
    }
    f[u].first=counter++;
}

void DFS_backward(int u){
    bvisited[u]=true;
    for(int v:rev[u]){
        if(!bvisited[v])
            DFS_backward(v);
    }
    scc[num_sccs].push_back(u);
}

void find_SCCs(){
    scc=vector<vector<int> >();
    scc.push_back(vector<int>());
    for(int i=0;i<V;++i){
        f[i].second=i;
    }
    counter=0;
    num_sccs=0;
    for(int i=0;i<V;++i){
        if(!fvisited[i]){
            DFS_forward(i);
        }
    }
    sort(f,f+V);
    for(int i=V-1;i>=0;--i){
        int u=f[i].second;
        if(!bvisited[u]){
            DFS_backward(u);
            num_sccs++;
            scc.push_back(vector<int>());
        }
    }
}

int main(){
    scanf("%d %d",&V,&E);
    for(int i=0;i<E;++i){
        int A,B;
        scanf("%d %d",&A,&B);--A;--B;
        adj[A].push_back(B);
        rev[B].push_back(A);
    }
    find_SCCs();
    printf("%d\n",num_sccs);
    for(int i=0;i<num_sccs;++i)
        sort(scc[i].begin(),scc[i].end());

    vector<pair<int,int> > s(num_sccs);
    for(int i=0;i<num_sccs;++i){
        s[i]=make_pair(scc[i][0],i);
    }
    sort(s.begin(),s.end());
    for(int i=0;i<num_sccs;++i){
        for(int j=0;j<scc[s[i].second].size();++j)
            printf("%d ",scc[s[i].second][j]+1);
        printf("-1\n");
    }
    return 0;
}

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

문제

문제

출처

ICPC

시간초과가 납니다

myju742 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말