(C++) 백준 16947 서울 지하철 2호선

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

1. cycle 찾기

현재 역 위치(x), 현재 경로에 포함된 역들을 넣은 벡터(v)를 인자로 하는 findCycle함수를 정의
처음 시작한 역과 끝나는 역이 같은 경우 cycle에 포함시켰다.

2. 두 역 사이의 거리 찾기

• 싸이클에 포함된 경우 : 순환선까지의 거리가 0이다.
• 싸이클에 포함되지 않은 경우 : dfs를 통해 순환선에 포함된 역을 찾는다.

엥 근디 최소거리 찾아야되면 bfs썼어야 됏을거같은데 어케맞앗지 ㅎㅋ -> 어차피 가는 경로가 두개 아님 한개밖에 없어서 상관없다~~

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

vector<vector<int>> stations(3005);
bool isvisited[3005];
bool iscycled[3005];
bool cycled = false;



void findCycle(int x, vector<int> &v){
    //cout<<'\n'<<x<<'\n';
    isvisited[x]=true;

    for(int i=0; i<stations[x].size(); i++){
        int next = stations[x][i];
       // cout<<"next : "<<next<<'\n';
        if(isvisited[next]) {
           if (v.size()!=2 && next==v[0]) {
                cycled=true;
                for(int i=0; i<v.size(); i++) {
                   // cout << "vector_ck : " << v[i] << '\n';
                    iscycled[v[i]] = true;
                }
                return ;
            }
        }
        else {
            v.push_back(next);
            findCycle(next, v);
            v.pop_back();
        }
    }

    isvisited[x]=false;
    return ;

}


void dfs(int x, int cnt, int start){

    isvisited[x]=true;

    for(int i=0; i<stations[x].size(); i++){
        int next = stations[x][i];
        if(isvisited[next]) continue;
        else {
            if(iscycled[next]) {
                cout<<cnt<<" ";
                isvisited[x]=false;
                return ;
            }
            else dfs(next, cnt+1, start);
        }
    }

    isvisited[x]=false;

}



int main(){

    int n; cin>>n;

    int x,y;
    for(int i=1; i<=n; i++){
        cin>>x>>y;
        stations[x].push_back(y);
        stations[y].push_back(x);
    }


    for(int i=1; i<=n ; i++){
        if(cycled) break;
        vector<int> v;
        v.push_back(i);
        findCycle(i, v);
    }
    memset(isvisited, false, sizeof(isvisited));

    for(int i=1; i<=n; i++){
      //  cout<<iscycled[i]<<'\n';
      if(iscycled[i]) cout<<0<<" ";
      else dfs(i, 1, i);
    }
}