\documentclass[12pt,addpoints]{exam}
\usepackage[utf8]{inputenc}
\usepackage{lastpage}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{array}
\usepackage{mdframed}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usepackage{algpseudocode}
\usepackage{hyperref}

% Paramètres globaux
%\qformat{\fbox{\textbf{Question \thequestion}} (\totalpoints \ \points)}
\bonuspointpoints{point \emph{bonus}}{points \emph{boni}}
\parindent 0cm
\hqword{Question}
\hpword{Sur}
\hsword{Note}
\htword{Total}

% Réponses
\printanswers

% En-tête et pieds de page
\headrule
\cfoot{\thepage /\pageref{LastPage}}
\lhead{INF7341 --- Structures de données}
\rhead{Hiver 2017}
\newcommand{\headrulewidth}{0.4pt}
\newcommand{\footrulewidth}{0.4pt}

% Boîtes
\newcommand\boite[1]{\begin{center} \begin{tikzpicture} \draw (0,0) rectangle (.99\linewidth, #1 cm); \end{tikzpicture} \end{center}}

% Colonnes mathématiques
\newcolumntype{L}{>{$}l<{$}}
\newcolumntype{C}{>{$}c<{$}}
\newcolumntype{R}{>{$}r<{$}}

% Raccourcis
\newcommand{\bigo}{\mathcal{O}}
\newcommand{\0}{\mathbf{0}}
\newcommand{\1}{\mathbf{1}}
\newcommand{\2}{\mathbf{2}}
\newcommand{\3}{\mathbf{3}}

% Algorithmes
\algrenewcommand\algorithmicwhile{\textbf{tant que}}
\algrenewcommand\algorithmicfunction{\textbf{fonction}}
\algrenewcommand\algorithmicend{\textbf{fin}}
\algrenewcommand\algorithmicdo{\textbf{faire}}
\algrenewcommand\algorithmicfor{\textbf{pour}}
\algrenewcommand\algorithmicif{\textbf{si}}
\algrenewcommand\algorithmicelse{\textbf{sinon}}
\algrenewcommand\algorithmicthen{\textbf{alors}}
\algrenewcommand\algorithmicreturn{\textbf{retourner}}
\algrenewcommand\algorithmicrepeat{\textbf{faire}}
\algrenewcommand\algorithmicuntil{\textbf{tant que}}
\newcommand{\enteteproc}[2]{\vskip\baselineskip \hspace*{\fill} \algorithmicprocedure~\Call{#1}{#2} \hspace*{\fill} \vskip\baselineskip}
\newcommand{\entetefunc}[3]{\vskip\baselineskip \hspace*{\fill} \algorithmicfunction~\Call{#1}{#2} : #3 \hspace*{\fill} \vskip\baselineskip}

% Code
\lstset{
  literate={é}{{\'e}}1
           {è}{{\`e}}1
           {ê}{{\^e}}1
           {î}{{\^i}}1
           {à}{{\`a}}1
           {É}{{\'E}}1,
  basicstyle=\footnotesize\ttfamily,
  keywordstyle=\bfseries\color{green!70!black},
  identifierstyle=\color{blue},
  commentstyle=\ttfamily\color{red!70!black}\emph,
  stringstyle=\bfseries\color{orange},
  showstringspaces=false,
  language=python,
  breaklines=true
}

% Types abstraits
\newcommand{\Booleen}{\mathrm{Booleen}}
\newcommand{\Naturel}{\mathrm{Naturel}}
\newcommand{\Entier}{\mathrm{Entier}}
\newcommand{\Pile}{\mathrm{Pile}}
\newcommand{\Sommet}{\mathrm{Sommet}}
\newcommand{\Ensemble}{\mathrm{Ensemble}}
\newcommand{\Graphe}{\mathrm{Graphe}}
\newcommand{\Association}{\mathrm{Association}}
\newcommand{\Arbre}{\mathrm{Arbre}}
\newcommand{\Foret}{\mathrm{Foret}}
\newcommand{\Element}{\mathrm{Element}}

% Opérations
\newcommand{\pileVide}{\textsc{pileVide}}
\newcommand{\estVide}{\textsc{estVide}}
\newcommand{\empiler}{\textsc{empiler}}
\newcommand{\depiler}{\textsc{depiler}}
\newcommand{\tete}{\textsc{tete}}
\newcommand{\sommets}{\textsc{sommets}}
\newcommand{\successeurs}{\textsc{successeurs}}
\newcommand{\associationVide}{\textsc{associationVide}}
\newcommand{\set}{\textsc{set}}
\newcommand{\get}{\textsc{get}}
\newcommand{\racine}{\textsc{racine}}
\newcommand{\arbre}{\textsc{arbre}}
\newcommand{\nombreNoeuds}{\textsc{nbNoeuds}}
\newcommand{\nombreFeuilles}{\textsc{nbFeuilles}}
\newcommand{\estFeuille}{\textsc{estFeuille}}
\newcommand{\ajouterEnfant}{\textsc{ajouterEnfant}}
\newcommand{\enfants}{\textsc{enfants}}
\newcommand{\foretVide}{\textsc{foretVide}}
\newcommand{\ajouterArbre}{\textsc{ajouterArbre}}
\newcommand{\nombreArbres}{\textsc{nbArbres}}


\begin{document}
	
\allowdisplaybreaks

\ifprintanswers
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Solution du devoir 3}}}
  \vskip 1.2cm
\else
  \vskip 1.2cm
  \centerline{\large\underline{\textbf{Devoir 3}}}
  \centerline{\small (à remettre au plus tard le 10 avril, à 16h00)}
  \centerline{\small (dans la chute du département d'informatique, située au PK-4150)}
  \vskip 1.2cm
Le devoir doit être rédigé \textbf{individuellement} et à l'\textbf{ordinateur}. Vous devez \textbf{justifier} chacune de vos réponses. La démarche ainsi que l'utilisation correcte de la notation mathématique seront évaluées. Tout retard entraînera une pénalité de \textbf{20\%} par jour (incluant les jours de la fin de semaine).
\fi

\ifprintanswers
  \begin{mdframed} \begin{center}
  \textbf{Auteur : (Indiquer votre nom ici)}
  \end{center} \end{mdframed}
\fi

\begin{center} \gradetable[h] \end{center}

\begin{questions}

% Composantes fortement connexes
\question (\totalpoints{} points)
En 1972, Tarjan a proposé un algorithme permettant de calculer les composantes fortement connexes d'un graphe orienté en temps linéaire, en une seule passe du graphe (voir l'entrée \href{https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm}{\color{blue}Wikipedia} sur le sujet). Dans cette question, nous nous intéressons à modifier l'implémentation de son algorithme pour qu'il retourne l'ensemble des composantes fortement connexes sous forme d'ensembles disjoints plutôt que de simplement afficher le contenu des composantes, comme c'est typiquement présenté.

\begin{parts}
  \part[20] Donnez le pseudocode de l'algorithme de Tarjan pour que celui-ci retourne des ensembles disjoints des sommets appartenant à chacune des composantes fortement connexes d'un graphe orienté quelconque $G$.
  \part En utilisant votre langage de programmation préféré parmi C, C++, Java et Python, implémentez votre algorithme. \emph{Contraintes~:} Vous n'avez pas le droit d'utiliser de bibliothèques de graphes ou d'ensembles disjoints. De plus, la structure de données d'ensembles disjoints doit être implémentée telle que vue classe, c'est-à-dire que la fusion doit se faire par rang et le calcul d'un représentant par compression de chemin. La répartition des points se fera comme suit~:
  \begin{subparts}
    \subpart[20] Structure d'ensembles disjoints;
    \subpart[20] Structure de graphe orienté;
    \subpart[20] Algorithme de Tarjan.
  \end{subparts}
\end{parts}
Proposez votre propre implémentation à partir du pseudocode, sans recopier une autre implémentation que vous pourriez trouver en ligne. Dans tous les cas, soyez bien prudents de citer toutes vos sources si vous vous basez fortement sur une d'entre elles.

% Files à priorité
\question (\totalpoints{} points)
Soit $F$ une file binomiale. Pour chacun des deux énoncés suivants, indiquez s'il est vrai ou faux. Appuyez votre réponse à l'aide d'une courte démonstration.
\begin{parts}
  \part[10] Si $F$ est initialement vide et qu'on y insère $n$ éléments quelconques, alors le coût total des insertions est $\bigo(n)$.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
  \part[10] Si $F$ contient $n$ éléments et qu'on effectue $m$ extractions du minimum, où $m \leq n$, alors le coût total des extractions est $\bigo(m)$.
  \begin{solution}
Ajouter votre solution ici
  \end{solution}
\end{parts}

\end{questions}

\end{document}
