글 읽기 - 유니온파인드로 풀었는데 시간초과가 뜨네요

tjrcjf410 3년 전 0

플로이드 와셜이 n^3 인데 이건 n^2이라 덜 걸릴줄 알았는데 어떻게 하면 시간을 더 단축시킬수 있을까요?

#include <iostream>
using namespace std;
int n,m;
int arr[201][201];
int p[201];
int route[201];
int find(int x){
    if(x==p[x]) return x;
    else return find(p[x]);
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) p[i]=i;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>arr[i][j];
            if(i==j) continue;
            if(arr[i][j]==1){
                int a = find(i);
                int b = find(j);
                if(a>b) p[a]=b;
                else if (a<b) p[b]=a;
            }
        }
    }
    for(int i=1; i<=m; i++)
        cin>>route[i];
    for(int i=1; i<=m-1; i++){
        int a = route[i];
        int b = route[i+1];
        a=find(a); b= find(b);
        if(a!=b){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
}

shg9411 3년 전 0

find 구현이 제대로 되어있지 않습니다.

tjrcjf410 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

유니온파인드로 풀었는데 시간초과가 뜨네요

tjrcjf410 3년 전 0

shg9411 3년 전 0

tjrcjf410 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말