BOJ 14675 ) 단절점과 단절선

 

14675번: 단절점과 단절선

주어진 트리에서 쿼리로 주어지는 정점과 간선이 해당 트리의 단절점 또는 단절선 인지(없을 경우 트리가 둘로 나뉘는지)를 묻는 문제이다. 한학기만에 알고리즘 문제를 풀었는데 너무 오랜만이라 완전히 방향을 잘못 잡았다. 고질병인 시간복잡도 계산 안하고 일단 문제 풀기는 여전히 고쳐지지 않았다. 정점의 개수 10만에 쿼리가 10만갠데 매 쿼리마다 dfs를 돌렸고 당연히 시간초과가 났다. 생각해보니까 당연한거였는데 왜 짤때는 모르는걸까.

 

주어진 그래프가 트리라 해당 노드가 리프나 루트노드를 제외하고는 모두 단절점이며 모든 간선이 단절선이 된다. 따라서 쿼리가 1 a로 주어지는 경우 a 정점으로 들어오는 간선의 개수가 몇개인지 세고 간선의 개수가 1개인 경우 단절점임을 파악할 수 있다. 쿼리가 2 a 로 주어지는 경우는 검사할 필요 없이 모든 간선이 단절선이므로 yes를 출력한다.

 

 

#include <iostream>
#include <vector>
using namespace std;

int N, q;
vector<int> indegree;
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>N;
    indegree=vector<int> (N+1);
    int a, b;
    for(int i=0;i<N-1;i++){
        cin>>a>>b;
        indegree[a]++;
        indegree[b]++;
    }
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>a>>b;
        if(a==1){
            (indegree[b]==1)?cout<<"no"<<'\n':cout<<"yes"<<'\n';
        }
        else{
            cout<<"yes"<<'\n';
        }
    }
    return 0;
}