Arbre intérieur maximal de l'anneau de base

Un.、Propriétés de l'arbre introverti de l'anneau de base：

1.C'est une image,Au lieu d'un arbre

2.Les sorties de tous les noeuds sont1

3.Les noeuds à l'extérieur de l'anneau pointent vers les noeuds à l'intérieur de l'anneau

2.、Comment trouver l'arbre intérieur de l'anneau de base：

Tri topologique：Enregistrer la pénétration de tous les noeuds,Après Tri topologique,La pénétration est1Le noeud de est un noeud dans l'anneau.

Dans le Codeg[i]Représentanti->g[i]Un côté dirigé de

    queue<int>q;
      for(int i=0;i<n;++i){
          if(degree[i]==0){
              q.push(i);
          }
      }
      while(!q.empty()){
          int cur=q.front();
          q.pop();
          if(--degree[g[cur]]==0){
              q.push(g[cur]);
          }
      }

Trois、Arbre à anneaux de base interne maximum：

Tous les degrés ne sont pas0Point,Vous pouvez trouver le plus grand anneau de base intérieur.

Attention pendant la traversée,Parce que tous les degrés sont1,Ainsi, la rencontre d'un noeud peut être réglée directement à0,Empêcher les traversées répétées.

 for(int i=0;i<n;++i){
          if(degree[i]==0){
              continue;
          }
          degree[i]=0;
          int max_ring_size=1;
          for(int v=g[i];v!=i;v=g[v]){
              ++max_ring_size;
              degree[v]=0;
          }
        ans=max(ans,max_ring_size);
      }