图论天坑

题目

---

题目链接: [https://www.luogu.org/problemnew/show/P2272]

题目索然看起来好像很清楚的样子，然而没人我知道中间的问号有什么用，直到我去网上查了一回 对于一张图G,它中间任意取上两个点u,v其中有一条u到 v 或者 v 到 u 的边，我们就称这张图为半连通图 如果从一张图G选出任意几个点与这几个点有关的所有的边，形成一张图G',如果G'是一张半连通图，我们就称G'为G的半连通子图 而在图G所有的G'中节点数最多的图，为图G的最大半连通子图 然后怎么做呢？ 首先，我们可以很清楚的知道，一张图中可能有多个环，而这个环中任意一个点到外面一个点，都可以形成一个半连通子图，我们根据每一个点来做太繁杂了 也就是说我们可以把环当做有权值一个点来判断，如果是自环权值为1就行了 怎么缩点(把环缩成点)相信大家心里都有数了，Tarjan判环，\(O(n+m)\)

关于 Tarjan 的做法，在这里不多做赘述，详情参照 uncle-lu 大佬的博客: [http://uncle-lu.org/archives/99]

但是 Tarjan 仅仅能够做到判断环,怎么缩点啊? 去当偶像吧建个新图啊! 怎么建呢?染色法: 通过将在同一环上的所有点标上一个编号(颜色),然后遍历所有点,把编号和编号相连接 至于后面的过程,我们首先可以知道,对于一个经过缩点后的图,它一定是一个森林,也就是说,我们只需要从入度为0的点开始查找就可以了 是不是有点懵?看一下代码把:

代码

---

#include <cstdio>
#include <cstring>
using namespace std;
// edge start
struct edge{
    int to,next;
}e[1100000],ne[1100000];
int ehead[110000],ecnt,necnt,nehead[1100000];
inline void add_edge(edge e[],int &ecnt,int ehead[],int from,int to){// add_edge 加边 因为要建两个图就传进来一些别的参数
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[from];
    ehead[from]=ecnt;
}
// edge end;
int n,m,mod,u,v,ans,acnt;
// n,m,mod,u,v 读入用,参照题意
// ans 最大点数 acnt 重复次数
// tarjan start
int DFN[110000],LOW[110000],huan[110000],time;// DFN[] LOW[] Tarjan 用 time 时间戳 huan[]记录权值
int s[1100000],scnt;// 堆栈
int col[110000],colcnt;// 记录每个点对应的颜色
bool vis[110000];// 记录访问次数
inline void tarjan(int now){// tarjan 标准 Tarjan
    DFN[now]=LOW[now]=++time;
    s[++scnt]=now;
    vis[now]=true;
    for(int i=ehead[now];i;i=e[i].next){
        if(!DFN[e[i].to]){
            tarjan(e[i].to);
            LOW[now]=LOW[now]<LOW[e[i].to]?LOW[now]:LOW[e[i].to];
        }
        else if(vis[e[i].to]){
            LOW[now]=LOW[now]<DFN[e[i].to]?LOW[now]:DFN[e[i].to];
        }
    }
    if(LOW[now]==DFN[now]){
        colcnt++;
        do{// 无论如何都要进行一遍,至少自己要加进去
            huan[colcnt]++;
            col[s[scnt]]=colcnt;
            vis[s[scnt]]=0;
            scnt--;
        }while(now!=s[scnt+1]);
    }
}
inline void tarjan_init(){// tarjan_iniit 标准 Tarjan
    for(int i=1;i<=n;i++) if(!DFN[i]) tarjan(i);
}
// tarjan end
bool cf(int from,int to){// cf 判断从from到to是不是已经有一条边
    for(int i=nehead[from];i;i=ne[i].next){// 遍历
        if(ne[i].to==to) return false;// 有返回否
    }
    return true;// 无返回是
}
inline void new_graph_build(){// new_graph_build建立新图
    for(int u=1;u<=n;u++){// 遍历点
        for(int i=ehead[u];i;i=e[i].next){// 遍历边
            if(col[u]==col[e[i].to]) continue;// 颜色相同为什么还要再加呢?
            if(cf(col[u],col[e[i].to])){// 判断有没有重复的边
                add_edge(ne,necnt,nehead,col[u],col[e[i].to]);// 加边
            }
            LOW[col[e[i].to]]++;// 判断入度,入度为0即为根
        }
    }
}
void find(int now){// 查找最大节点数
    vis[now]=true;// 不能重复查找一个边
    for(int i=nehead[now];i;i=ne[i].next){
        if(!vis[ne[i].to]) find(ne[i].to);// 没有找过再找
        DFN[now]=DFN[now]>DFN[ne[i].to]?DFN[now]:DFN[ne[i].to];// 去最大的情况
    }
    DFN[now]+=huan[now];// 别忘了自己还有权
}
void find_cnt(int now){
    vis[now]=true;// 不能重复查找
    for(int i=nehead[now];i;i=ne[i].next){
        if(!vis[ne[i].to]) find_cnt(ne[i].to);
        if(DFN[now]==huan[now]+DFN[ne[i].to]) col[now]=(col[now]+col[ne[i].to])%mod;// col[] 有多少个和当前节点当前最多节点相同的节点(多读几遍
    }
    if(!nehead[now]) col[now]=1;// 如果这个点没有边的话别忘记自环
    if(DFN[now]==ans) acnt=(acnt+col[now])%mod;// 如果是最大情况的话往答案上加wq
}
int main(){
// 读入
    scanf("%d%d%d",&n,&m,&mod);
    for(int i=1;i<=m;i++) {scanf("%d%d",&u,&v);add_edge(e,ecnt,ehead,u,v);}
    tarjan_init();// Tarjan
    memset(DFN,0,sizeof(DFN));// 没有用的数组可不能够浪费
    memset(LOW,0,sizeof(LOW));
    new_graph_build();
    memset(vis,false,sizeof(vis));
    memset(col,0,sizeof(col));
    for(int i=1;i<=colcnt;i++){
        if(LOW[i]==0){// 如果是根的话
            find(i);
            ans=ans>DFN[i]?ans:DFN[i];// 寻找最大答案
        }
    }
    memset(vis,false,sizeof(vis));
    //memset(DFN,0,sizeof(DFN));
    for(int i=1;i<=colcnt;i++){
        if(LOW[i]==0){// 从根找
            find_cnt(i);
        }
    }
    printf("%d\n%d",ans,acnt);// 输出
}

End

---

不管如何在这道题目里多少还是有点树型DP的影子的,不过图论题目要小心,错一个变量很难看出来的… ]]>