图论天坑
题目
题目链接: [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 仅仅能够做到判断环,怎么缩点啊?
代码
#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的影子的,不过图论题目要小心,错一个变量很难看出来的… ]]>