2018年1月22日训练日记

xiaoxiao2021-02-28  4

今天主要学习了图论算法知识里的强连通分量部分。代码模板基本都是一样的,关键是理解。理解之后就感觉简单多了。

主要是学会求连通分量的个数以及哪些点属于哪些连通分量。这里附上个人Tarjan算法模板代码:

void tar(int k) {     low[k]=dfn[k]=++ti;     us[k]=1;     sta[++f]=k;     for(int i=he[k];i!=-1;i=a[i].nex)     {         int v=a[i].v;         if(!dfn[v])         {          tar(v);          low[k]=min(low[k],low[v]);         }         else if(us[v]) low[k]=min(low[k],dfn[v]);     }     if(low[k]==dfn[k])     {         cnt++;         do{             j=sta[f--];             us[j]=0;             sum[j]=cnt;         }while(j!=k);     } } void solve() {  for(int i=1;i<=n;i++)  if(!dfn[i]) tar(i);//zhu yi!!!这里dfn注意清零  //cout<<cnt<<endl;  if(cnt!=1) puts("No");  else puts("Yes"); }

另外就是看了无向图求割顶与桥的模板,看了几个模板,存边都没用链式前向星,而是用的vector,不知道这对结果是否有什么影响。

下面附上例题poj 2117 求割顶数量的核心代码:

int dfs(int u,int fa) {     int lowu;     pre[u]=lowu=++ti;     int cm=0;     for(int i=0;i<vc[u].size();i++)     {         int v=vc[u][i];         if(!pre[v])         {          cm++;          int lowv=dfs(v,u);          lowu=min(lowu,lowv);          if(lowv>=pre[u]) ok[u]=1;//不要少了=,WA了一次,最后ok[i]=1即i为割顶         }         else if(pre[v]<pre[u]&&v!=fa)         lowu=min(lowu,pre[v]);     }     if(fa<0&&cm==1) ok[u]=0;     return low[u]=lowu; }

目前准备多看几个博客和例题,争取理解透彻,能随时写出模板代码。

明天的主要任务是看无向图双连通分量的知识,总结一下,理解透彻原理及模板代码并正确熟练地敲出来,做几道经典例题。

一会儿去补昨天的EOJ月赛题目。。。

转载请注明原文地址: https://www.6miu.com/read-2350368.html

最新回复(0)