P2272 [ZJOI2007]最大半连通子图
斯德哥尔摩
2018-07-30 23:26:20
[P2272 [ZJOI2007]最大半连通子图](https://www.luogu.org/problemnew/show/P2272)
首先一个强连通缩点，把图变成一个$DAG$。
然后就是求最长链与最长链个数。
求最长链就直接拓扑排序一下。
个数呢？
这个要$DP$一下。
本蒟蒻看到$DP$就不会了。。。
设$f[i]$表示图中以$i$为终点的最长链个数，则$f[i]$等于与$i$连通并且距离是起点到$i$的最长距离的点的$f$值之和。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#define MAXN 100010
using namespace std;
int n,m,p,c=1;
int num[MAXN],head[MAXN],indegree[MAXN],vis[MAXN],f[MAXN],g[MAXN];
struct Graph{
int next,to;
}a[MAXN*10];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void add(int x,int y){
a[c].to=y;a[c].next=head[x];head[x]=c++;
}
namespace Tarjan{
int c=1,d=1,s=0,top=1;
int cstack[MAXN],head[MAXN],deep[MAXN],low[MAXN],colour[MAXN];
bool vis[MAXN];
struct Graph{
int next,to;
}edge[MAXN*10];
inline void add_edge(int x,int y){
edge[c].to=y;edge[c].next=head[x];head[x]=c++;
}
void work(int x){
deep[x]=low[x]=d++;
vis[x]=true;
cstack[top++]=x;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].to;
if(!deep[v]){
work(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])
low[x]=min(low[x],deep[v]);
}
if(low[x]>=deep[x]){
s++;
do{
colour[cstack[top-1]]=s;
vis[cstack[top-1]]=false;
}while(cstack[--top]!=x);
}
}
void solve(){
int x,y;
for(int i=1;i<=m;i++){
x=read();y=read();
add_edge(x,y);
}
for(int i=1;i<=n;i++)if(!deep[i])work(i);
for(int i=1;i<=n;i++)num[colour[i]]++;
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=edge[j].next){
int v=edge[j].to;
if(colour[v]!=colour[i]){
add(colour[i],colour[v]);
indegree[colour[v]]++;
}
}
n=s;
}
}
void topsort(){
int u,v;
queue<int> q;
for(int i=1;i<=n;i++){
if(!indegree[i])q.push(i);
f[i]=num[i];g[i]=1;
}
while(!q.empty()){
u=q.front();
q.pop();
for(int i=head[u];i;i=a[i].next){
v=a[i].to;
indegree[v]--;
if(!indegree[v])q.push(v);
if(vis[v]==u)continue;
if(f[u]+num[v]>f[v]){
f[v]=f[u]+num[v];
g[v]=g[u];
}
else if(f[u]+num[v]==f[v])g[v]=(g[v]+g[u])%p;
vis[v]=u;
}
}
}
void work(){
int maxn=0,ans=0;
for(int i=1;i<=n;i++){
if(f[i]>maxn){maxn=f[i];ans=g[i];}
else if(f[i]==maxn)ans=(ans+g[i])%p;
}
printf("%d\n%d\n",maxn,ans);
}
void init(){
n=read();m=read();p=read();
Tarjan::solve();
topsort();
}
int main(){
init();
work();
return 0;
}
```