P2272 [ZJOI2007]最大半连通子图
题目描述
一个有向图\(G=(V,E)\)称为半连通的\((Semi-Connected)\)，如果满足：\(\forall u,v \in V\)，满足\(u \to v\)或\(v \to u\)，即对于图中任意两点\(u\)，\(v,\)存在一条\(u\)到\(v\)的有向路径或者从\(v\)到\(u\)的有向路径。若\(G'=(V',E')\)满足\(V' \in V\)，\(E'\)是\(E\)中所有跟\(V'\)有关的边，则称\(G'\)是\(G\)的一个导出子图。若\(G'\)是\(G\)的导出子图，且\(G'\)半连通，则称\(G'\)为\(G\)的半连通子图。若\(G'\)是\(G\)所有半连通子图中包含节点数最多的，则称\(G'\)是\(G\)的最大半连通子图。给定一个有向图\(G\)，请求出\(G\)的最大半连通子图拥有的节点数\(K\)，以及不同的最大半连通子图的数目\(C\)。由于\(C\)可能比较大，仅要求输出\(C\)对\(X\)的余数。
输入输出格式
输入格式：
第一行包含两个整数\(N\)，\(M\)，\(X\)。\(N\)，\(M\)分别表示图\(G\)的点数与边数，X的意义如上文所述接下来\(M\)行，每行两个正整数\(a\),\(b\)，表示一条有向边\((a,b)\)。图中的每个点将编号为\(1,2,3…N\)，保证输入中同一个\((a,b)\)不会出现两次。
输出格式：
应包含两行，第一行包含一个整数\(K\)。第二行包含整数\(C\) \(Mod\) \(X\).
说明
对于100%的数据， \(N \le 100000, M \le 1000000, X \le 10^8\)
这种题先缩点都成套路了吧
考虑在一个有向无环图中半联通图是什么，结果是一条链，直接做DP就行了
但是！！
这个题一定要考虑重边
Code：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
const int N=100010;
const int M=1000010;
int head0[N],Next0[M],to0[M],cnt0;
void add0(int u,int v)
{
Next0[++cnt0]=head0[u];to0[cnt0]=v;head0[u]=cnt0;
}
int head[N],Next[M],to[M],cnt;
void add(int u,int v)
{
Next[++cnt]=head[u];to[cnt]=v;head[u]=cnt;
}
int dfn[N],low[N],in[N],s[N],ha[N],siz[N],time,tot;
int n,m,n_,cntt;
ll p;
pair <int,int > e[M];
void tarjan(int now)
{
dfn[now]=low[now]=++time;
s[++tot]=now;
in[now]=1;
for(int i=head0[now];i;i=Next0[i])
{
int v=to0[i];
if(!dfn[v])
{
tarjan(v);
low[now]=min(low[now],low[v]);
}
else if(in[v])
low[now]=min(low[now],dfn[v]);
}
if(low[now]==dfn[now])
{
int k,Siz=0;
n_++;
do
{
k=s[tot--];
Siz++;
ha[k]=n_;
in[k]=0;
}while(k!=now);
siz[n_]=Siz;
}
}
void New()
{
for(int i=1;i<=n;i++)
{
for(int j=head0[i];j;j=Next0[j])
{
int v=to0[j];
if(ha[v]!=ha[i])
e[++cntt]=make_pair(ha[i],ha[v]);
}
}
sort(e+1,e+1+cntt);
cntt=unique(e+1,e+1+cntt)-(e+1);
for(int i=1;i<=cntt;i++)
{
in[e[i].second]++;
add(e[i].first,e[i].second);
}
}
void init()
{
scanf("%d%d%lld",&n,&m,&p);
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add0(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
memset(in,0,sizeof(in));
New();
}
ll Cnt[N],ans;
int dp[N],mx;
queue <int > q;
void work()
{
for(int i=1;i<=n_;i++)
if(!in[i])
{
q.push(i);
dp[i]=siz[i];
mx=max(mx,dp[i]);
Cnt[i]=1;
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=Next[i])
{
int v=to[i];
if(dp[v]<dp[u]+siz[v])
{
dp[v]=dp[u]+siz[v];
Cnt[v]=Cnt[u];
mx=max(mx,dp[v]);
}
else if(dp[v]==dp[u]+siz[v])
(Cnt[v]+=Cnt[u])%=p;
in[v]--;
if(!in[v]) q.push(v);
}
}
for(int i=1;i<=n_;i++)
if(dp[i]==mx)
(ans+=Cnt[i])%=p;
printf("%d\n%lld\n",mx,ans);
}
int main()
{
init();
work();
return 0;
}
2018.7.26