#include <iostream>
#include <vector>
#include <stack>
int n;
using namespace std;
vector < int > graph[ 1000006 ] ;
int components[ 1000006 ] ;
int no_of_components;
stack < int > mystack;
int main( ) {
// Load the graph
cin >> n;
for ( int i= 0 ; i< n; i++ ) {
int X;
cin >> X;
graph[ X- 1 ] .push_back ( i) ;
}
// Display loaded graph
cout << "Graph:" << endl;
for ( int i= 0 ; i< n; i++ ) {
cout << "Node " << i<< " --> " ;
for ( auto & x : graph[ i] )
cout << x<< " " ;
cout << endl;
}
cout << endl;
// Identify the connectect groups
for ( int i= 0 ; i< n; i++ ) {
if ( components[ i] > 0 )
continue ;
no_of_components++ ;
mystack.push ( i) ;
components[ i] = no_of_components;
while ( mystack.empty ( ) == false ) {
int v;
v= mystack.top ( ) ;
mystack.pop ( ) ;
for ( int u= 0 ; u< graph[ v] .size ( ) ; u++ ) {
if ( components[ graph[ v] [ u] ] > 0 ) continue ;
mystack.push ( graph[ v] [ u] ) ;
components[ graph[ v] [ u] ] = no_of_components;
}
}
}
// Display resutls
cout << "Number of connected components: " << no_of_components<< endl;
for ( int i= 0 ; i< n; i++ )
cout << "Node " << i<< " is in component " << components[ i] << endl;
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RhY2s+CgppbnQgbjsKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZlY3RvciA8aW50PiBncmFwaFsxMDAwMDA2XTsKaW50IGNvbXBvbmVudHNbMTAwMDAwNl07CmludCBub19vZl9jb21wb25lbnRzOwpzdGFjayA8aW50PiBteXN0YWNrOwoKaW50IG1haW4oKXsKCiAgICAvLyBMb2FkIHRoZSBncmFwaAogICAgCiAgICBjaW4gPj4gbjsKICAgIGZvciAoaW50IGk9MDsgaTxuOyBpKyspewogICAgICAgIGludCBYOwogICAgICAgIGNpbiA+PiBYOwogICAgICAgIGdyYXBoW1gtMV0ucHVzaF9iYWNrKGkpOyAKICAgIH0KICAgIAogICAgLy8gRGlzcGxheSBsb2FkZWQgZ3JhcGggCiAgICBjb3V0PDwiR3JhcGg6Ijw8ZW5kbDsgCiAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSB7CiAgICAJY291dCA8PCAiTm9kZSAiPDxpPDwiIC0tPiAiOwogICAgCWZvciAoYXV0byAmeCA6IGdyYXBoW2ldKSAKICAgIAkgICAgY291dDw8IHg8PCAiICI7CiAgICAJY291dDw8ZW5kbDsgICAgIAogICAgfSAgCiAgICBjb3V0PDxlbmRsOyAKCiAgICAvLyBJZGVudGlmeSB0aGUgY29ubmVjdGVjdCBncm91cHMgCiAgICAKICAgIGZvciAoaW50IGk9MDsgaTxuOyBpKyspewoKICAgICAgICBpZiAoY29tcG9uZW50c1tpXT4wKSAKICAgICAgICAgICAgY29udGludWU7CgogICAgICAgIG5vX29mX2NvbXBvbmVudHMrKzsKCiAgICAgICAgbXlzdGFjay5wdXNoKGkpOwogICAgICAgIGNvbXBvbmVudHNbaV09bm9fb2ZfY29tcG9uZW50czsKCiAgICAgICAgd2hpbGUgKG15c3RhY2suZW1wdHkoKT09ZmFsc2UpewogICAgICAgICAgICBpbnQgdjsKCiAgICAgICAgICAgIHY9bXlzdGFjay50b3AoKTsKICAgICAgICAgICAgbXlzdGFjay5wb3AoKTsKCiAgICAgICAgICAgIGZvciAoaW50IHU9MDsgdTxncmFwaFt2XS5zaXplKCk7IHUrKyl7CiAgICAgICAgICAgICAgICBpZiAoY29tcG9uZW50c1tncmFwaFt2XVt1XV0+MCkgY29udGludWU7CgogICAgICAgICAgICAgICAgbXlzdGFjay5wdXNoKGdyYXBoW3ZdW3VdKTsKICAgICAgICAgICAgICAgIGNvbXBvbmVudHNbZ3JhcGhbdl1bdV1dPW5vX29mX2NvbXBvbmVudHM7CgogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIC8vIERpc3BsYXkgcmVzdXRscwogICAgCiAgICBjb3V0IDw8ICJOdW1iZXIgb2YgY29ubmVjdGVkIGNvbXBvbmVudHM6ICI8PG5vX29mX2NvbXBvbmVudHM8PGVuZGw7CiAgICBmb3IgKGludCBpPTA7aTxuOyBpKyspIAogICAgICAgY291dCA8PCJOb2RlICI8PCBpPDwiIGlzIGluIGNvbXBvbmVudCAiPDxjb21wb25lbnRzW2ldPDxlbmRsOwoKICAgIHJldHVybiAwOwoKfQ==