Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define loop(i, n) for (int i=0;i<n;i++)
- #define lv(i, v) for (int i=0;i<adj[v].size();i++)
- #define MAXN INT_MAX
- #define F first
- #define S second
- using namespace std;
- const int MAX = 5e5+9;
- const int MIN = 1e3+9;
- int arr[MAX],A[MAX];
- bool vis[MAX],done[MAX];
- vector <int> adj[MAX];
- void DFS (int v){
- done [v] = 1;
- lv (i, v){
- int u = adj[v][i];
- if (!done[u]){
- DFS (u);
- }
- }
- }
- int check (int v){
- vis[v] = 1;
- lv (i, v){
- int u = adj[v][i];
- //cout << u << " " << v << " " << arr[u] << endl;
- if (u == v) return u;
- else if (vis[u]) return MAX;
- check (u);
- }
- }
- int main ()
- {
- int n, root = -1, temp , res = 0, t = 1;
- scanf("%d", &n);
- loop (i, n) {
- scanf("%d", &arr[i]);
- arr[i]--;
- A[i] = arr[i];
- if (arr[i] == i) root = i ;
- }
- cout << root << endl ;
- loop (i, n){
- adj[i].pb(arr[i]);
- }
- loop (i,n){
- memset(vis, 0, sizeof(vis));
- temp = check(i);
- cout << temp << " " << check(i) << endl ;
- if (i == root || done [i]) continue ;
- else if (temp == MAX && temp != root){
- A[i] = root;
- DFS (i);
- }
- else {
- A[temp] = root ;
- DFS (i);
- }
- }
- //loop(i, n)
- // if (arr[i] != A[i]) res++;
- //printf("%d\n",res);
- //loop(i, n)
- // printf("%d ",A[i]+1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement