1093: [ZJOI2007]最大半连通子图
Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 2767 Solved: 1095
[Submit][Status][Discuss]
Description
一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意
两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'?V，E'是E中所有跟V'有关的边，
则称G'是G的一个导出子图。若G'是G的导出子图，且G'半连通，则称G'为G的半连通子图。若G'是G所有半连通子图
中包含节点数最多的，则称G'是G的最大半连通子图。给定一个有向图G，请求出G的最大半连通子图拥有的节点数K
，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。
Input
第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整
数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。N ≤1
00000, M ≤1000000；对于100%的数据， X ≤10^8
Output
应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.
Sample Input
1 2
2 1
1 3
2 4
5 6
6 4
Sample Output
3
HINT
Source
先缩点，重新建图，使其成为一个 DAG，
DAG 中每个点有一个点权表示这个点是原图中的几个点缩成的
新图中的一个最大半连通子图，必然是新图中的一个最长链（点权和最大），
知道了这点之后，DP 就行了，
类似于树形 DP，先求出从每个点出发，能走的最长链是多长，统计最长的那条就是最大半连通子图的点的数量了，
至于怎么求有多少个最大半连通子图，也是一样的 DP 就行，在上一步的 DP 之后，再 DP 一遍，统计每个点出发能走出多少条最长链，最后统计求和即可
/*
Problem:
OJ:
User: S.B.S.
Time:
Memory:
Length:
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<iomanip>
#include<cassert>
#include<climits>
#include<functional>
#include<bitset>
#include<vector>
#include<list>
#include<map>
#define F(i,j,k) for(int i=j;i<=k;i++)
#define M(a,b) memset(a,b,sizeof(a))
#define FF(i,j,k) for(int i=j;i>=k;i--)
#define BUG system("pause")
#define maxn 200000
#define inf 0x3f3f3f3f
#define maxm 5000000
//#define LOCAL
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int head[maxn],to[maxm],next[maxm];
int dfn[maxn],low[maxn];
int st[maxm],ed[maxm];
int n,m,cnt,ans,anss,mod;
int tot,belong[maxn],t,p,stk[maxn],val[maxn];
bool instk[maxn];
int num[maxn],in[maxn],dp[maxn],q[maxm],vis[maxn];
inline void add(int u,int v)
{
to[cnt]=v;
next[cnt]=head[u];
head[u]=cnt++;
}
inline void init()
{
memset(head,-,sizeof(head));cnt=;
cin>>n>>m>>mod;
for(int i=;i<=m;i++)
{
cin>>st[i]>>ed[i];
add(st[i],ed[i]);
}
}
inline void dfs(int u)
{
low[u]=dfn[u]=++t;
stk[++p]=u; instk[u]=true;
for(int i=head[u];i!=-;i=next[i])
{
if(!dfn[to[i]])
{
dfs(to[i]);
low[u]=min(low[u],low[to[i]]);
}
else if(instk[to[i]]) low[u]=min(low[u],dfn[to[i]]);
}
if(dfn[u]==low[u])
{
tot++;
int tmp=-;
while(tmp!=u)
{
tmp=stk[p--];
belong[tmp]=tot;
val[tot]++;
instk[tmp]=false;
}
}
}
inline void topsort()
{
int h=,t=,u;
for(int i=;i<=tot;i++)
if(in[i]==)
{
q[t++]=i;
dp[i]=val[i];
num[i]=;
}
while(h<t)
{
u=q[h++];
for(int i=head[u];i!=-;i=next[i])
{
in[to[i]]--;
if(in[to[i]]==) q[t++]=to[i];
if(vis[to[i]]==u) continue;
if(dp[to[i]]<dp[u]+val[to[i]])
{
dp[to[i]]=dp[u]+val[to[i]];
num[to[i]]=num[u];
}
else if(dp[to[i]]==dp[u]+val[to[i]])
{
num[to[i]]=(num[to[i]]+num[u])%mod;
}
vis[to[i]]=u;
}
}
}
inline void go()
{
for(int i=;i<=n;i++) if(!dfn[i]) dfs(i);
memset(head,-,sizeof(head));cnt=;
for(int i=;i<=m;i++)
if(belong[st[i]]!=belong[ed[i]])
{
add(belong[st[i]],belong[ed[i]]);
in[belong[ed[i]]]++;
}
topsort();
for(int i=;i<=tot;i++)
{
if(dp[i]>ans)
{
ans=dp[i];
anss=num[i];
}
else if(dp[i]==ans) anss=(anss+num[i])%mod;
}
cout<<ans<<endl<<anss<<endl;
}
int main()
{
std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
init();
go();
return ;
}