Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

TIMUS 1742

Autor: Lucas Castro


#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

#define TAM 1000123

int n;
int ini;
int fila[TAM];
int foi[TAM];
int prox[TAM];

class progs{
public:
  int id,ge;

  progs(int _id, int _ge){
    id = _id;
    ge = _ge;
  }

  bool operator < (progs p) const{
    return ge < p.ge;
  }

};

void DFS(int v){

  foi[v] = 1;
  int pv = prox[v];

  if(pv < n && pv != -1 && !foi[pv])
    if(!foi[pv])
      DFS(pv);  

  fila[ini++] = v;
}

int main(){
  int p;

  scanf(" %d",&n);  
  vector<progs> prog;  
  prog.clear();
  for(int i = 0 ; i < n ; i++){
    prog.push_back(progs(i,0));
  }

  memset(prox,-1,sizeof(prox));
  //  cout << prox[0] << endl;
  for(int i = 0 ; i < n ; i++){      
    scanf(" %d",&p);    
    p--;    
    if(p < n){
      prox[i] = p;    
      prog[p].ge++;
    }    
  }

  sort(prog.begin(),prog.end());

  memset(foi,0,sizeof(foi));
  ini = 0;
  int ansmin = 0;
  for(int i = 0 ; i < n ; i++){
    int id = prog[i].id;
    if(!foi[id]){
      DFS(id);      
      ansmin++;
    }
  }

  int ansmax = 0;
  memset(foi,0,sizeof(foi));
  for(int i = 0 ; i < ini ; i++){
    int id = fila[i];    
    if(id < n){
      if(!foi[id]){
        DFS(id);      
        ansmax++;
      }    
    }
  }

  printf("%d %d\n",ansmin,ansmax);  
  return 0;
}