题解 P2272 【[ZJOI2007]最大半连通子图】
swiftc
2019-07-29 12:05:32
__排版哪里有问题啊QAQ__
根据题意,一个强连通分量一定是半联通子图,所以多个强联通分量也一定是半联通子图,所以问题就转化成了在一个缩点后的图上找最长链,步骤如下:
### 1.缩点
先用tarjan记录每一个强联通分量的大小和每个点在哪个强连通分量里
```cpp
void tarjan(int now){
if(vis[now])return;
dfn[now]=low[now]=++Time;
tmp.push(now);
vis[now]=1;
for(int i=head[now];i;i=nxt[i]){
if(!dfn[to[i]]){
tarjan(to[i]);
low[now]=min(low[now],low[to[i]]);
}else if(vis[to[i]]){
low[now]=min(low[now],dfn[to[i]]);
}
}
if(low[now]==dfn[now]){
_cnt++;
while(tmp.top()!=now){
vis[tmp.top()]=0;
in[tmp.top()]=_cnt;
siz[_cnt]++;
tmp.pop();
}
tmp.pop();
vis[now]=0;
in[now]=_cnt;
siz[_cnt]++;
}
}
```
如果有两个有边连接的点不在一个强连通分量里,那么这两个强连通分量之间就有边,我这里直接把缩点后的图新建在另一个前向星里了,注意要去重,即不能在两个强连通分量间建多条边。
```cpp
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=nxt[j]){
if(in[i]!=in[to[j]]){
bool flag=0;
for(int ii=_head[in[i]];ii;ii=_nxt[ii]){
if(_to[ii]==in[to[j]])flag=1;
}
if(flag)continue;
_nxt[++__cnt]=_head[in[i]];
_head[in[i]]=__cnt;
_to[__cnt]=in[to[j]];
du[in[to[j]]]++;
}
}
}
```
### 2.求最长链
最后用拓扑排序来DP求最长链:先把入度为0的强连通分量放入队列,每次取出第一个开始更新,```num[i]```表示以i为结尾的最长链有几个```ans[i]```表示最长链的长度,更新时如果可以让以这个点结尾的链变得更长,就把```num[i]```设为1,更新```ans[i]```,如果又发现一条和以这个点结尾最长链一样长的链,就把```num[i]+=1```,最后找最大值即可
```cpp
queue<int>q;
for(int i=1;i<=_cnt;i++){
if(du[i]==0)q.push(i);
ans[i]=siz[i];
num[i]=1;
}
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=_head[now];i;i=_nxt[i]){
if(ans[_to[i]]<ans[now]+siz[_to[i]]){
ans[_to[i]]=ans[now]+siz[_to[i]];
num[_to[i]]=num[now];
}
else if(ans[_to[i]]==ans[now]+siz[_to[i]]){
num[_to[i]]=(num[now]%x+num[_to[i]]%x)%x;
}
du[_to[i]]--;
if(du[_to[i]]==0){
q.push(_to[i]);
}
}
}
```
完整代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
int du[3000001],head[3000001],nxt[3000001],to[3000001],dfn[3000001],low[3000001],vis[3000001],in[3000001],siz[3000001];
int n,m,x,cnt,Time,_cnt,__cnt;
stack<int>tmp;
void tarjan(int now){
if(vis[now])return;
dfn[now]=low[now]=++Time;
tmp.push(now);
vis[now]=1;
for(int i=head[now];i;i=nxt[i]){
if(!dfn[to[i]]){
tarjan(to[i]);
low[now]=min(low[now],low[to[i]]);
}else if(vis[to[i]]){
low[now]=min(low[now],dfn[to[i]]);
}
}
if(low[now]==dfn[now]){
_cnt++;
while(tmp.top()!=now){
vis[tmp.top()]=0;
in[tmp.top()]=_cnt;
siz[_cnt]++;
tmp.pop();
}
tmp.pop();
vis[now]=0;
in[now]=_cnt;
siz[_cnt]++;
}
}
int _head[3000001],_nxt[3000001],_to[3000001],ans[3000001],num[3000001];
int maxn=-1,id;
int main(){
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
nxt[++cnt]=head[a];
head[a]=cnt;
to[cnt]=b;
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=nxt[j]){
if(in[i]!=in[to[j]]){
bool flag=0;
for(int ii=_head[in[i]];ii;ii=_nxt[ii]){
if(_to[ii]==in[to[j]])flag=1;
}
if(flag)continue;
_nxt[++__cnt]=_head[in[i]];
_head[in[i]]=__cnt;
_to[__cnt]=in[to[j]];
du[in[to[j]]]++;
}
}
}
queue<int>q;
for(int i=1;i<=_cnt;i++){
if(du[i]==0)q.push(i);
ans[i]=siz[i];
num[i]=1;
}
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=_head[now];i;i=_nxt[i]){
if(ans[_to[i]]<ans[now]+siz[_to[i]]){
ans[_to[i]]=ans[now]+siz[_to[i]];
num[_to[i]]=num[now];
}
else if(ans[_to[i]]==ans[now]+siz[_to[i]]){
num[_to[i]]=(num[now]%x+num[_to[i]]%x)%x;
}
du[_to[i]]--;
if(du[_to[i]]==0){
q.push(_to[i]);
}
}
}
int maxn1=-1,maxn2=-1;
for(int i=1;i<=_cnt;i++){
if(ans[i]>maxn1){
maxn1=ans[i];
maxn2=num[i];
}
else if(ans[i]==maxn1){
maxn2=(maxn2%x+num[i]%x)%x;
}
}
printf("%d\n%d\n",maxn1,maxn2);
return 0;
}
```