当前位置:网站首页>Arbre intérieur maximal de l'anneau de base

Arbre intérieur maximal de l'anneau de base

2022-01-15 02:25:33 Yan Wei, Digital Media Technology, Jiangnan University

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);
      }

版权声明
本文为[Yan Wei, Digital Media Technology, Jiangnan University]所创,转载请带上原文链接,感谢
https://chowdera.com/2022/01/202201080600041637.html

随机推荐