제출 #88966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88966		Lkvatashidze	특수한 그래프 (IZhO13_specialg)	C++17	0 / 100	1072 ms	8204 KiB

specialg

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

    int n, m;
    map < int, int > mp;
    int g[100005];
    int BFS(int,int);

 int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

     cin >> n;
     for (int k=1; k<=n; k++) {
         int x;
          cin >> x;
          g[k]=x;
     }

    cin >> m;
     while (m--) {
        int type;
        cin >> type;
        if (type==1) {
           int x;
            cin >> x;
           mp[x]=true;
        }
        else{
            int a, b;
        cin >> a >> b;

            int ans=BFS(a,b);
        cout << ans << '\n';
        }
    }


    return 0;
}
   int BFS (int s, int fin) {

     vector < bool > used(n+1,0);
     vector < int > d(n+1,0);
     queue < int > Q;

     Q.push(s);
     used[s]=true;

      while (!Q.empty()) {
         int v=Q.front();
         Q.pop();
         if (mp[v]) continue;
         if (used[g[v]]) continue;
         d[g[v]]=d[v]+1;
         Q.push(g[v]);
         used[g[v]]=true;
      }
       if (used[fin]==0)
        return -1;

       return d[fin];
}

• Subtask 1: 0 / 100