Guest User

Untitled

a guest
Jun 16th, 2012
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MN = 1000 * 100 + 10;
  7.  
  8. vector <int> g[MN];
  9.  
  10. int color[MN], k = 0;
  11.  
  12. void dfs(int v) {
  13.     color[v] = k;
  14.     for(int i = 0;  i< g[v].size(); i ++) {
  15.         int to = g[v][i];
  16.         if (!color[to])
  17.             dfs(to);
  18.     }
  19. }
  20.  
  21. int main () {
  22.     //freopen ("input.txt","r",stdin);
  23.     //freopen("output.txt", "w", stdout);
  24.     int n, m;
  25.     cin >> n >> m;
  26.     for(int i = 1; i <= n; i ++) {
  27.         int from;
  28.         cin >> from;
  29.         g[from].push_back(i);
  30.     }
  31.     g[1].push_back(2);
  32.     g[2].push_back(1);
  33.     for(int i = 1; i <= n; i ++) {
  34.         if (!color[i]) {
  35.             k ++;
  36.             dfs(i);
  37.         }
  38.     }
  39.     for(int i = 0; i < m; i ++) {
  40.         int a, b;
  41.         cin >> a >> b;
  42.         if (color[a] == color[b])
  43.             printf("Yes\n");
  44.         else printf("No\n");
  45.     }
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment