Voyons une manière de s’organiser afin de travailler efficacement. Nous illustrons notre exemple en résolvant le problème suivant:
Étant une liste de prénoms composés uniquement de [a-zA-Z], écrivez pour chaque prénom, Bonjour prénom !
Commençons par créer le fichier contenant un exemple d’entrée dans un fichier hello.in:
Luke
Leia
Han
Chewbacca
R2D2
BenPuis le fichier contenant la sortie attendue hello.res:
Bonjour Luke !
Bonjour Leia !
Bonjour Han !
Bonjour Chewbacca !
Bonjour R2D2 !
Bonjour Ben !Nous pouvons maintenant commencer à coder dans un fichier hello.cpp:
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;
while(cin >> s)
cout << "Bonjour " << s << " !\n";
}Quelques remarques sur ce code:
#include<iostream> permet d’utiliser cin et cout afin de lire l’entrée et écrire la sortie.#include<string> permet d’utiliser les stringusing namespace std permet d’éviter de devoir préfixer les objets de la librairie standard de std::. Vu que les programmes d’EPS sont courts et ne peuvent rien inclure hors de la STL cela ne pose pas de problème.Il faut ensuite compiler ce programme. À l’école le compilateur est g++. Il est fortement conseiller d’activer les warnings et on va également utiliser certaines extensions de c++17 vous compilez donc avec g++ -Wall -Wextra -std=c++17 hello.cpp qui vous produit un exécutable a.out.
Vous pouvez maintenant tester votre programme. Comme il lit sur l’entrée standard il faut rediriger le contenu de votre fichier d’entrée sur l’entrée standard ./a.out < hello.in. La sortie est alors affichée sur la sortie standard, vous pouvez alors regarder si le programme vous semble correct.
Attention votre sortie doit être exactement la même que la sortie attendue, vous pouvez donc utiliser diff pour vérifier que votre sortie est exactement la bonne. ./a.out < hello.in > hello.out permet de rediriger la sortie dans votre programme dans le fichier hello.out. Ensuite la commande diff hello.out hello.res vous permet de vous assurer que les deux fichiers sont identiques et vous affiche les différences dans le cas contraire.
Enfin votre programme doit s’exécuter assez rapidement, si vous avez un jeu de données sensiblement de même taille que celui attendu vous pouvez regarder le temps que met votre programme à traiter ce jeu de données. Pour cela compilez avec les optimisations g++ -O2 -Wall -Wextra -std=c++17 hello.cpp, puis vous pouvez utiliser time ./a.out < hello.in > hello.out. Si votre programme est trop lent vous pouvez le stopper en faisant Ctrl + c.
Dans chaque problème il faudra lire sur l’entrée standard et écrire sur la sortie standard. Certains problèmes ne sont pas spécialement pensés pour faciliter la lecture d’entrée, heureusement C++ dispose de plusieurs fonctions qui vous faciliteront la partie entrée sortie. Nous vous conseillons fortement d’utiliser les fonctions cin/cout du C++ plutôt que scanf/printf de C.
Les fonctions les plus utilisées seront >> et <<. getline pourra parfois nous être utile. Il est possible de mettre >> et getline dans la condition d’une boucle while pour lire entièrement un flux de taille arbitraire.
Dans les cas simples et fréquents, >> lit un stream et interprète les données. Il saute les caractères blancs et s’arrête à la fin du flux. Attention la position dans le flux est juste après le mot lu.
getline lit une ligne entière. Attention en le combinant avec << on peut facilement lire uniquement le caractère de retour de ligne au lieu de la ligne suivante. Dans ce cas on peut utiliser ignore pour extraire sans traiter les caractères blancs.
Voici un exemple sur ce fichier d’entrée. (3.23e3 est le nombre 3230 en notation scientifique)
12 3.23e3
Coucou@&#. p
Paf c
c
Hello
World !#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
double d;
string s;
char c;
cin >> n >> d >> s >> c;
//n=12, d=3230, s=Coucou@&#., c=p
cin.ignore();
getline(cin, s);
cin >> c;
//s="Paf c";
//c='c'
getline(cin, s);
//s="\n"
cin >> s;
//s=="Hello"
cin.ignore();
getline(cin, s);
//s="World !"
}Par défaut cin saute les caractères blancs (espace tabulation et retour de ligne), si vous voulez vraiment lire caractère par caractère il faut passer le manipulateur noskipws. Pour revenir dans l’état normal il faut ensuite passer le manipulateur skipws. Voici un exemple:
#include<iostream>
#include<sstream>
using namespace std;
int main(){
char a, b, c;
{
istringstream iss (" 123");
iss >> skipws >> a >> b >> c;
cout << a << b << c << '\n';
}
{
istringstream iss (" 123");
iss >> noskipws >> a >> b >> c;
cout << a << b << c << '\n';
}
}qui affiche
123
1Nous avons vu qu’il était facile de traiter un fichier avec un nombre arbitraire de lignes. Voyons comment adapter ceci pour traiter une ligne avec un nombre arbitraire d’entiers à traiter.
Nous allons lire toute la ligne d’un coup avec getline, et transformer la chaine obtenue en flux afin de pouvoir utiliser la même méthode que pour lire le fichier.
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
int main(){
string s;
//commençons par lire la ligne
getline(cin, s);
//transformons ensuite notre chaine de caractères en un flux de lecture
istringstream ss(s);
//nous pouvons maintenant utiliser ss comme cin
int tmp;
while(ss >> tmp)
cout << tmp;
}Rien de compliqué, mais il faut le savoir, le manipulateur setprecision(n) permet d’afficher les nombres à virgule avec une précision de n. Le manipulateur fixed permet lui de forcer l’affichage des 0 non significatifs.
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
double a=1.2, b=1.23456789123456789;
cout << a << ' ' << b << '\n';
cout << fixed << setprecision(6) << a << ' ' << b << '\n';
}affiche
1.2 1.23457
1.200000 1.234568C’est un problème assez délicat qui dépend pas mal de la plateforme (cygwin sous windows est extrêmement mauvais par exemple), mais en général il est dit que scanf/printf sont plus rapides que cin/cout. En fait par défaut cin/cout sont synchronisés sur scanf/printf ce qui explique leurs lenteurs. Si vous n’utilisez pas scanf/printf cette synchronisation est inutile, vous pouvez la désactiver. De plus votre programme étant testé en mode non interactif, vous n’avez pas non plus besoin de la synchronisation entre cin et cout. Sans cette synchronisation (et ça dépend des plateformes et du compilateur) cin/cout sont globalement aussi rapides que scanf/printf. Notez que cette optimisation n’est utile que lorsque les entrées sorties ne sont pas négligeables devant la complexité de votre algorithme (i.e. votre algo est au pire en O(n ln(n))).
Pour désactiver ces synchronisations il suffit d’utiliser sync_with_stdio et .tin, voici un exemple.
#include<iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tmp;
while(cin >> tmp)
cout << tmp << '\n';
}Pour représenter les nombres, vous pouvez vous limiter à trois types:
double dès que les nombres considérés ne sont pas entiers, utilisez des doubles.int pour les entiers inférieurs à 109.long long pour les entiers jusqu’à 1018.Attention utiliser des int à la place de long long est sensiblement plus rapide (i.e. certains problèmes ne valideront pas avec des long long).
Attention également aux calculs intermédiaires qui ne doivent pas dépasser la capacité du type. Par exemple si on prend cet extrait de code d’une exponentiation modulaire rapide avec a, tmp et MOD des entiers inférieurs à 109
long long a,tmp,MOD;
return (a*tmp*tmp)%MOD;Donne un résultat faux, en effet le produit a*tmp*tmp peut dépasser 1018 même si on en prend ensuite le modulo, il faut donc prendre le modulo des résultats intermédiaires.
int a,tmp,MOD;
return (a*((tmp*tmp)%MOD))%MOD;Donne également un résultat incorrect, car les produits intermédiaires dépassent la capacité d’un int.
long long a,tmp,MOD;
return (a*((tmp*tmp)%MOD))%MOD;est la version correcte.
Vector est un conteneur pour les tableaux dynamiques. Les fonctions les plus utiles sont l’opérateur [] et la fonction push_back. push_back permet d’insérer en fin de tableau une nouvelle valeur, cela agrandit le tableau en temps constant amorti. L’opérateur [] permet d’accéder à la nème valeur du tableau en temps constant. Les indices commencent à partir de 0 jusqu’à la taille du vector-1. Le tri de tableau existe dans la bibliothèque de template algorithm.
Voici un exemple simple d’utilisation.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
//crée un tableau t de 5 entiers (1,2,3,4,5)
vector<int> t{1,2,3,4,5};
//crée un tableau d de 12 flotants initialisés à 3.14
vector<double> d(12,3.14);
cout << d[0] << '\n';
//crée un tableau p de char de taille 0
vector<char> p;
p.push_back('z');
//p est maintenant de taille 1 et contient 'z';
p.push_back('a');
//p est maintenant de taille 2 et contient 'z' puis 'a';
//affiche le tableau p
for(int i=0;i<int(p.size());++i)
cout << p[i] << ' ';
cout << '\n';
sort(begin(p), end(p));
//p est maintenant de taille 2 et contient 'a' puis 'z';
//une autre manière d'afficher le tableau p
for(char c:p)
cout << c << ' ';
cout << '\n';
}Qui affiche:
3.14
z a
a zMap est un conteneur permettant d’utiliser des tableaux associatifs triés par clé supportant des opérations en O(lg(n)). L’opérateur le plus utile est [key] qui permet d’accéder à la valeur stockée pour key. Attention si cette valeur n’existe pas elle est crée avec l’initialisateur par défaut (pour les int c’est 0).
Vous pouvez voir les autres fonctions utiles des map ici
Voici un exemple simple d’utilisation.
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
map<char,string> mymap;
mymap['b']="another element";
mymap['a']="an element";
mymap['c']=mymap['b'];
cout << "mymap['a'] is " << mymap['a'] << '\n';
cout << "mymap['b'] is " << mymap['b'] << '\n';
cout << "mymap['c'] is " << mymap['c'] << '\n';
cout << "mymap['d'] is " << mymap['d'] << '\n';
//version pre c++17
//for(map<char,string>::iterator it=mymap.begin();it!=mymap.end();++it)
// cout << "key: " << it->first << ", value: " << it->second << '\n';
for(auto& x:mymap)
cout << "key: " << x.first << ", value: " << x.second << '\n';
}qui affiche:
mymap['a'] is an element
mymap['b'] is another element
mymap['c'] is another element
mymap['d'] is
key: a, value: an element
key: b, value: another element
key: c, value: another element
key: d, value:Supposons que vous vouliez une structure de donnée pour représenter un cercle. Vous voulez également pouvoir utiliser des vector<cercle> ainsi que d’autres conteneurs de cercles. Il faut pour cela créer votre propre structure de données. Le mot clé est struct et il faut également définir un constructeur (une fonction membre sans type de retour du même nom que votre struct). Attention il y a un ; à la fin de la déclaration. Voici un exemple:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct mycercle{
int x,y,r;
//notez le c=1, qui rend le troisième paramètre optionnel
//s'il n'est pas spécifié ce sera 1
mycercle(int a, int b, int c=1){
x=a;
y=b;
r=c;
}
//Une déclaration équivalente
//mycercle(int a, int b, int c=1):x(a),y(b),r(c){}
//on peut aussi spécifier un opérateur de comparaison afin
//d'utiliser les algorithmes de la STL
//que se passe t'il si je compare mon cercle avec un autre cercle c
//noter les const qui permettent de s'assurer qu'aucun cercle ne sera
//modifié durant la comparaison
//ici un cercle est plus petit qu'un autre s'il a plus petit rayon.
bool operator<(const mycercle& c) const{
return r<c.r;
}
};
//le mot clé const permet de s'assurer que c ne sera pas modifié
//le & permet de passer c par référence
void affiche(const mycercle& c){
cout << "Le cercle a pour centre " << c.x << ','
<< c.y << " et pour rayon " << c.r <<'\n';
}
int main(){
mycercle C1(0,0,2);
affiche(C1);
//Le cercle a pour centre 0,0 et pour rayon 2
mycercle C2(2,7);
affiche(C2);
//Le cercle a pour centre 2,7 et pour rayon 0
vector<mycercle> t1;
//vector<mycercle> t2(5);
//Ne fonctionne pas, car il n'y a pas de constructeur par défaut
//il faut au choix donner des valeurs par défaut à tous les paramètres
//du constructeur ou faire un constructeur sans paramètres
vector<mycercle> t3{mycercle{1,2,3}, mycercle{4,5,6}};
sort(begin(t3), end(t3));
}Le but de cet algorithme est de calculer une plus longue sous suite croissante d’une chaine x donnée en entrée.
La première idée est de calculer la plus longue sous suite commune à x et à sort(begin(x), end(x)). On peut faire cela avec une programmation dynamique où t[i][j] est la taille de la plus longue sous suite commune entre les i premier nombre de x et les j premier de sort(begin(x), end(x)). Il n’y a rien de très compliqué mais l’algorithme final est en O(n2). Voyons comment résoudre ce problème en O(n ln(n)).
Pour résoudre ce problème nous allons utiliser un tableau m tel que m[i] contient l’indice du plus petit entier qui termine une LIS de taille i+1. (le +1 n’est là que car les tableaux sont numeroté à partir de 0). La taille de la plus grande LIS est donc la taille du tableau m.
On lit la séquence x dans l’ordre et on met à jour m. Cet algo est simple à coder et fonctionne en temps O(n2), en effet pour mettre à jour m on doit parcourir tout le tableau m et trouver l’indice i tels que t[m[i]]<curr<t[m[i+1]]. Le point clé pour accélerer cet algo est de remarquer que le tableau t[m[i]] est trié. En effet si on a une LIS de taille k finissant par n, on a également une LIS de taille k-1 finissant par n. On peut donc trouver l’indice de mise à jour du tableau m en temps logarithmique.
Parfois la seule solution à un problème est de tester toutes les solutions possible. Voyons trois types de choses que l’on peut générer et comment faire.
Pour générer tous (2n) les sous ensembles, d’un ensemble on peut utiliser le codage binaire d’un entier pour représenter les élements choisi du sous-ensemble. Si le ième bit est à 1 on prend le ième élément dans le sous ensemble. Pour ce genre de code il est bon de connaitre les opérations bit à bit.
En voici certaines: ~ fait le “non” bit à bit, | le “ou”, & le “et” et ^ le “xor”. Il y a également les opérateurs de décalage. n<<i décale les bits de n de i cran vers la gauche, n>>i les décale vers la droite. Pour calculer 2n on peut par exemple faire 1<<n.
Voici un exemple de code pour générer les sous ensembles.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
vector<int> t{1,2,3};
int n=t.size();
for(int i=0;i<(1<<n);++i){
for(int j=0;j<n;++j)
if((i>>j)&1)
cout << t[j] << ' ';
cout << '\n';
}
}En utilisant la même idée de représentation d’ensemble par des bits, on peut générer les sous-ensembles de taille exactement k. Un hack connu du à Gosper permet de calculer le prochain sous-ensemble en temps constant, le code est assez cryptique mais c’est bon de savoir qu’il existe.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
vector<int> t{1,2,3,4,5};
int n=t.size();
int k=3;
int set = (1 << k) - 1;
while (set < (1<<n)) {
for(int j=0;j<n;++j)
if((set>>j)&1)
cout << t[j] << ' ';
cout << '\n';
// Gosper's hack:
int c = set & -set;
int r = set + c;
set = (((r^set) >> 2) / c) | r;
}
}Une autre génération possible est celle de toutes les permutations. Un algorithme existe pour en temps linéaire mais amorti constant calculer la permutation suivante dans l’ordre lexicographique. Cet algorithme est dans la librairie standard sous le nom next_permutation. Il agit sur un conteneur et le modifie.
Avant de voir un exemple d’utilisation, quelques remarques. Il permet de générer les permutation dans l’ordre lexicographique donc si vais faites une boucle do while sur un tableau non trié, il n’affichera pas les première permutation. De même si votre tableau comporte des doublons, vous aurez moins de n! permutations.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
vector<int> t{1,2,3};
sort(begin(t), end(t));
do{
for(int x:t)
cout << x << ' ';
cout << '\n';
}while(next_permutation(begin(t), end(t)));
}On veut une structure de donnée simulant un tableau t et permettant de répondre efficacement aux requêtes suivantes: incremente(i, val) incremente la case i de tableau de la valeur val (val peut être négatif), et somme(i,j) calcule la somme t[i]+t[i+1]+…+t[j].
Deux solutions sont simples, la première consiste à stocker le tableau tel quel et faire une boucle pour le calcul de la somme. Nous avons alors une complexité en < O(1), O(n) > .
Une autre solution qui est l’opposé de celle-ci est de stocker les sommes préfixes. C’est à dire, utiliser un tableau t' avec t’[i]=t[0]+…t[i]. Le calcul de somme est alors en temps constant (somme(i,j)=t'[j]-t'[i-1]) en revanche la mise à jour d’une case modifie toutes les cases suivantes. Nous avons alors une complexité en < O(n), O(1) > .
Dans ces deux cas la complexité en mémoire est linéaire.
Voyons une solution de complexité < O(ln(n)), O(ln(n)) > utilisant également un espace mémoire linéaire. Cette structure de donnée s’appelle arbre de Fenwick ou Binary Indexed Tree (BIT) suivant les pays. Elle est particulièrement courte (20 lignes) à coder (quand on connait certaines astuces), elle a donc tout à fait sa place dans un poly d’EPS.
La première remarque est que si l’on sait répondre à la requête somme(0,j) on sait répondre aux requêtes somme(i,j) car somme(i,j)=somme(0,j)-somme(0,i-1). Avec la convention que somme(0,i) avec i<0 vaut 0.
L’idée est d’utiliser la solution des sommes préfixes avec une granularité plus fine. Nous allons utiliser un tableau t' tel que t'[i] contient la somme t[erase(i)]+...+t[i] où si l’écriture binaire de i est x01…1 alors l’écriture binaire de erase(i) est x00…0.
Par exemple: * erase(11)=8 * erase(15)=0
Maintenant le calcul de somme(0,i) est simple il s’agit de t'[i]+somme(0,erase(i)-1).
Pour effectuer l’opération d’incrément de la case i=x01…1, il faut mettre à jour la case d'indice i det', puis la case d'indice next(i)=x11…1 où on a remplacé le 0 le plus à droite par un 1, puis la case d'indice next(next(i)), et ainsi de suite en remplaçant au fur et à mesure les 0 par des 1 de droite à gauche.
Dans les deux cas (si le calcul de l’indice suivant est en temps constant), le nombre d’opérations est borné par la taille de l’écriture binaire de i. Nous avons bien des opérations qui s’effectuent en temps < O(ln(n)), O(ln(n)) > .
Voyons comment calculer erase(i), il faut remplacer le bloc de 1 de poids faible par un bloc de 0. Notons que si i=x01…1, i+1=x10…0. On a alors erase(i)= i & (i+1). Pour calculer l’indice suivant dans l’opération d’incrément, notons que si i=x01…1, next(i)=x11…1. On peut alors remarquer que next(i)=i | (i+1).
int somme(int x, int y, const vector<int> & t){
if(x==0){
int res=0;
while(y>=0){
res+=t[y];
y=(y&(y+1))-1;
}
return res;
}
else
return somme(0,y,t)-somme(0,x-1,t);
}
void incremente(int x, int inc, vector<int> & t) {
while(x<int(t.size())){
t[x]+=inc;
x=x|(x+1);
}
}On cherche à trier lexicographiquement tous les suffixes d’une chaine de caractères. On veut également pouvoir rapidement répondre aux requêtes demandant le plus grand préfixe commun (LCP) au suffixe commençant à la ième lettre et celui commençant à la jème lettre.
Par exemple, le suffixe array (SA) de “bobocel” est:
On peut créer tous les suffixes de la chaine, il y en a n, puis les trier. On a alors Onlg(n) comparaison mais attention une comparaison de chaines se fait en la longueur de la chaine. On a donc une complexité en O(n2lg(n)). On peut simplement répondre aux requêtes LCP en O(n).
On va construire la matrice P telle que P[i][j] contient la position lexicographique de la chaine si…si + 2j parmi tous les facteurs de taille 2j de s (Avec la convention qu’un facteur qui déborde de la chaine est complété par des caractères blancs). Attention, si deux facteurs sont identiques ils doivent avoir la même position. On note qu’il y a seulement besoin de O(ln(n)) lignes dans la matrice (les lignes suivantes étant toujours les mêmes). Et que la dernière ligne correspond bien à la position du suffixe commençant en i parmi tous les suffixes.
Voyons comment construire ce tableau. La première ligne est la position d’une lettre (chaine de taille 1) parmi l’ensemble des lettres. En pratique comme ce qui nous intéresse est l’ordre relatif des chaines (i.e. on veut que si s < t alors la position de s soit inférieur à la position de t) on peut simplement utiliser le numéro de la lettre. Par exemple si l’alphabet est les minuscules anglaise, la position peut être donnée par lettre-'a'.
Voyons maintenant comment construire la ligne j à partir de la ligne j − 1. Il suffit de savoir comparer la position de deux chaines de taille 2j, ensuite on peut utiliser un tri pour connaitre leur position. Or si s et t sont deux chaines de même taille, s < t si et seulement si s est plus petite que t sur sa première moitié ou ces moitiées sont égales et s est plus petite que t sur sa deuxième moitiée. La position de la chaine commençant en i de taille 2j est alors la position (attention toujours au cas d’égalité) de (P[i][j − 1], P[i + 2j − 1][j − 1]) (attention si i + 2j − 1 est plus grand que la taille de la chaine on compléte avec des blancs et donc P[i][j − 1] = − 1) dans l’ensemble de ces couples.
Pour chaque ligne la complexité est celle de calculer la position d’une paire dans un ensemble de n paires et on a O(ln(n)) lignes à calculer. Si on trie pour calculer la position on a alors un algorithme en O(nln2(n)).
Remarque: Vu que l’on trie des couples d’entiers entre − 1 et n on peut en fait les trier en temps linéaire on a alors une complexité en O(nln(n)). En pratique on peut faire un tri radix stable sur la seconde composante de la paire puis sur la première, mais attention en pratique le gain est assez faible, et le risque est de faire une erreur lors du tri. Il est donc conseillé d’avoir le code dans le poly ou simplement d’utiliser sort de la STL.
Avec cette matrice on peut également répondre rapidement O(ln(n)) à la question: quel est le plus grand préfixe commun entre le suffixe commençant en i et celui commençant en j ?. Et sachant répondre à cette question il est facile de répondre à la question de connaitre le plus long préfixe entre le ième et le jème suffixe de s dans l’ordre lexicographique.
L’idée est de regarder les positions des facteurs pour des tailles de facteur de plus en plus petite. Si la position pour une taille k i.e. P[i][k]==P[j][k] alors les facteurs sont les mêmes sur les 2k premiers caractères et on regarde les facteurs commençant en i + 2k et j + 2k, sinon les facteurs ne sont pas les mêmes sur la taille 2k mais ils peuvent l’être sur une taille plus petite, on regarde donc le facteur commençant en i et celui commençant en j de taille 2k − 1.
L’application la plus classique est, étant donné un ensemble de chaines, trouver le plus grand facteur commun à ces chaines. Pour cela on calcule le suffix array combiné (par exemple en concatenant avec un délimiteur toutes les chaines) de toutes les chaines et on cherche pour toute fenêtre contenant un mot de chaque chaine le plus long prefixe commun entre le suffixe débutant la fenêtre et celui le terminant. Par construction c’est un préfixe de l’ensemble des suffixes de la fenêtre c’est donc un facteur d’au moins un suffixe par chaine et donc un facteur de chaque chaine.
Il faut utiliser setfill choisir le caractère de remplissage et setw pour choisir la taille du remplissage. Ces deux fonctions sont dans iomanip
#include <iostream>
#include <iomanip>
using namespace std;
int main () {
cout << setfill ('0') << setw (5);
cout << 77 << endl;
}qui affiche
00077Sauf exception (Floyd-Warshall par exemple) il est préférable de stocker le graphe sous forme de listes d’adjacences. Attention si vous codez un parcours un profondeur récursivement, il y a de forte chance que sur un gros graphe la pile d’appel explose provocant une segfault (d’un autre coté certains algorithmes sont bien plus simple à écrire récursivement).
Un sommet d’articulation est un sommet tel que le supprimer rend le graphe non connexe. Un pont est une arête telle que la supprimer rend le graphe non connexe. Un algorithme naif, serait de tester pour chaque sommet et chaque arête si sa suppression déconnecte le graphe. On a alors un algorithme quadratique, voyons comment trouver tous les sommets d’articulation et ponts en temps linéaire grâce à un parcours en profondeur (DFS).
Il est plus simple de coder cet algorithme récursivement. Pour chaque sommet u, on va garder le temps où il a été visité pour la première fois dfs_num[u] et le plus petit dfs_num apparaissant sur un sommet du sous arbre de dfs enraciné en u, on note cette valeur dfs_low[u]. Si on code récursivement on peut simplement initialiser dfs_low[u]=dfs_num[u]. Puis après chaque appel récursif sur un fils (même ceux déjà visité mais par pour son père) v de u faire dfs_low[u] = min(dfs_low[u], dfs_low[v]).
Il est facile de voir si un sommet u avec un fils v vérifie dfs_low[v] >= dfs_num[u], alors u est un sommet d’articulation. Attention il y a un cas spécial pour la racine de l’arbre de dfs. En adaptant la condition, on peut facilement savoir si l’arête uv est un pont.