您的位置: 首页  >  IT文章  >  BZOJ1093 [ZJOI2007]最大半连通子图

BZOJ1093 [ZJOI2007]最大半连通子图

分类: IT文章 • 2022-08-01 22:51:15

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

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

Sample Output

3
3
这道题首先用tarjan缩点，因为强连通分量必然能放在一个半连通子图里。
之后图变为DAG 拓扑排序dp即可。
f[i]表示到i的最大半连通子图，sl[i]表示i这个强连通分量的点数,sum[i]表示方案数%k。
f[v]=max(f[u]+sl[v])u为所有能到达v的点。
sum[v]=sigema（sum[u]）f[u]+sl[v]==f[v]
这里要注意，两点间可能有重边，要做判断防止一个点被加两遍。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct X
{
    int v,n,f;
}x[1000005],y[1000005];
const int N=1e5+5;
int s,st[N],top,dfn[N],low[N],pa[N],cnt,t,w=-1,q[N],syg[N];
bool vis[N],sf[N];
void add(int u,int v)
{
    y[++s].n=y[u].f;
    y[y[u].f=s].v=v;
}
void dfs(int u)
{
    dfn[u]=low[u]=++s;
    vis[st[++top]=u]=sf[u]=1;
    for(int i=x[u].f;i;i=x[i].n)
        if(!vis[x[i].v]) dfs(x[i].v),low[u]=min(low[x[i].v],low[u]);
        else if(sf[x[i].v]) low[u]=min(low[u],dfn[x[i].v]);
    if(dfn[u]==low[u])
    {
        pa[u]=++cnt;
        for(;st[top]!=u;top--)
            pa[st[top]]=cnt,sf[st[top]]=0;
        top--;sf[u]=0;
    }
}
int main()
{
    int n,m,mod;
    scanf("%d%d%d",&n,&m,&mod);
    for(int i=1;i<=m;i++)
    {
        int u;
        scanf("%d%d",&u,&x[i].v);
        x[i].n=x[u].f;
        x[u].f=i;
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]) dfs(i);
    memset(st,0,sizeof(st));
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    s=0;
    for(int i=1;i<=n;i++)
    {
        st[pa[i]]++;
        for(int j=x[i].f;j;j=x[j].n)
            if(pa[i]!=pa[x[j].v]) add(pa[i],pa[x[j].v]),++dfn[pa[x[j].v]];
    }
    memset(pa,0,sizeof(pa));
    memset(low,0,sizeof(low));
    for(int i=1;i<=cnt;i++)
        if(!dfn[i]) vis[q[++w]=i]=1,low[i]=1,pa[i]=st[i];
    for(;t<=w;t++)
    {
        for(int i=y[q[t]].f;i;i=y[i].n)
            if(!vis[y[i].v])
            {
                dfn[y[i].v]--;
                if(!dfn[y[i].v]) vis[q[++w]=y[i].v]=1;
                if(syg[y[i].v]==q[t]) continue;
                syg[y[i].v]=q[t];
                if(st[y[i].v]+pa[q[t]]>pa[y[i].v])
                {
                    pa[y[i].v]=pa[q[t]]+st[y[i].v];
                    low[y[i].v]=low[q[t]];
                }
                else if(st[y[i].v]+pa[q[t]]==pa[y[i].v]) low[y[i].v]+=low[q[t]],low[y[i].v]%=mod;
            }
    }
    int ans1=0,ans2;
    for(int i=1;i<=cnt;i++)
        if(ans1<pa[i]) ans1=pa[i],ans2=low[i];
        else if(ans1==pa[i]) ans2+=low[i],ans2%=mod;
    printf("%d
%d",ans1,ans2);
    return 0;
}

相关推荐