백준 16965 구간과 쿼리

 

https://www.acmicpc.net/problem/16965

16965번: 구간과 쿼리

그래프 탐색을 사용하는 문제였습니다.

이 문제에서 주의할점은 문제에서 주어진 조건을 만족하는 두 구간 사이의 이동이 양방향이 아니라는점입니다. 즉 무방향 그래프가 아니라는점입니다. 처음에는 저도 Union-Find를 사용해서 풀기를 시도하였고 틀리고나서 문제를 다시 읽다보니위에서 말한 점을 깨닫게 되었습니다. 

 

쿼리가 구간을 추가하는 쿼리일때 이전에 추가했던 구간들과 현재 추가하는 구간을 비교하며 간선을 추가하고 

두 구간의 이동이 가능한지 묻는 쿼리일때는 그래프탐색을 통해 확인하여 출력하면됩니다.

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
vector<pair<int,int>> V;
vector<vector<int>> E(101,vector<int>());
bool visit[101];
void dfs(int now){
    visit[now]=true;
    for(int x=0;x<E[now].size();x++){
        if(!visit[E[now][x]]){
            dfs(E[now][x]);
        }
    }
}
int main(){
    int Q;
    cin>>Q;
    int Vcount=0;
    for(int query=1;query<=Q;query++){
        int q,x,y;
        cin>>q>>x>>y;
        if(q==1){
            V.push_back({x,y});
            for(int nowv=0;nowv<Vcount;nowv++){ 
                 if((V[nowv].first>x && V[nowv].first<y) || (V[nowv].second>x && V[nowv].second<y)){
                     E[nowv].push_back(Vcount);
                 }
                if((x>V[nowv].first && x<V[nowv].second) || (y>V[nowv].first && y<V[nowv].second)){
                    E[Vcount].push_back(nowv);
                }
            }
            Vcount++;
        }
        else{
            x--;
            y--;
            for(int nowv=0;nowv<Vcount;nowv++){
                visit[nowv]=false;
            }
            dfs(x);
            if(visit[y]){
                cout<<1<<'\n';
            }
            else{
                cout<<0<<'\n';
            }
        }
    }
}