题意

题目描述

一个有向图\(G=(V,E)\)称为半连通的\((Semi-Connected)\)，如果满足：\(\forall u,v\in V\)，满足\(u\rightarrow v\)或\(v\rightarrow u\)，即对于图中任意两点\(u,v\),存在一条\(u\)到\(v\)的有向路径或者从\(v\)到\(u\)的有向路径。若\(G^\prime=(V^\prime,E^\prime)\)满足\(V^\prime\in V\)，\(E^\prime\)是\(E\)中所有跟\(V^\prime\)有关的边，则称\(G^\prime\)是\(G\)的一个导出子图。若\(G^\prime\)是\(G\)的导出子图，且\(G^\prime\)半连通，则称\(G^\prime\)为\(G\)的半连通子图。若\(G^\prime\)是\(G\)所有半连通子图中包含节点数最多的，则称\(G^\prime\)是\(G\)的最大半连通子图。给定一个有向图\(G\)，请求出\(G\)的最大半连通子图拥有的节点数\(K\)，以及不同的最大半连通子图的数目\(C\)。由于\(C\)可能比较大，仅要求输出\(C\)对\(X\)的余数。

输入格式

第一行包含两个整数\(N,M,X\)。\(N,M\)分别表示图\(G\)的点数与边数，\(X\)的意义如上文所述接下来M行，每行两个正整数\(a,b\)，表示一条有向边\((a,b)\)。图中的每个点将编号为\(1,2,3\dots N\)，保证输入中同一个\((a,b)\)不会出现两次。

输出格式

应包含两行，第一行包含一个整数\(K\)。第二行包含整数\(C\mod X\)。

输入输出样例

输入样例#1：

6 6 20070603

1 2

2 1

1 3

2 4

5 6

6 4

输出样例#1：

3

3

说明

对于\(100\%\)的数据，\(N\le 100000,M\le 1000000,X\le 10^8\)。

思路

先来想两个问题：

该图是强连通图，那么答案是多少？
该图是有向无环图，那么答案是多少？

对于第一个问题，任意两点互相可达，问题变得很简单，答案就是原图；对于第二个问题，我们可以直接\(DAG\ DP\)完美解决。

那么对于任意的一张图，我们用\(Tarjan\)缩点之后，答案不久呼之欲出了吗？所以这题只需要在缩点之后的图上\(DP\)就好了。

不过还有个细节：因为要求方案数，所以不能建重边。比如点\(1\)向点\(2\)建了两条边。从\(1\)点向周围拓展时，第一次扫描到\(2\)，我们更新了\(2\)的答案；第二次扫描到\(2\)，我们又更新了\(2\)的答案。这显然是不被允许的。所以开个\(set\)判断一下重边就好啦。

AC代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<LL,LL> PLL;

const LL MAXN=1e5+5,MAXM=1e6+5;

LL n,m,p,ans1,ans2,tot,dfn[MAXN],low[MAXN];

LL cnt,top[MAXN],to[MAXM],nex[MAXM];

LL _cnt,_top[MAXN],_to[MAXM],_nex[MAXM];

LL js,bel[MAXN],sz[MAXN],deg[MAXN],val[MAXN],tms[MAXN];

bool vis[MAXN];

stack<LL>S;

set<PLL>SS;

LL read()

{

    LL re=0;char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();

    return re;

}

void tarjan(LL now)

{

    dfn[now]=low[now]=++tot,vis[now]=true,S.push(now);

    for(LL i=top[now];i;i=nex[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(dfn[now]==low[now])

    {

        bel[now]=++js,vis[now]=false,sz[js]=1;

        while(S.top()!=now) bel[S.top()]=js,vis[S.top()]=false,sz[js]++,S.pop();

        S.pop();

    }

}

void work()

{

    memset(vis,false,sizeof vis);

    queue<LL>Q;

    for(LL i=1;i<=js;i++) if(!deg[i]) val[i]=sz[i],tms[i]=1,Q.push(i);

    while(!Q.empty())

    {

        LL now=Q.front();Q.pop();

        for(LL i=_top[now];i;i=_nex[i])

        {

            deg[_to[i]]--;

            if(vis[_to[i]]) continue;

            vis[_to[i]]=true;

            if(val[_to[i]]<val[now]+sz[_to[i]]) val[_to[i]]=val[now]+sz[_to[i]],tms[_to[i]]=tms[now];

            else if(val[_to[i]]==val[now]+sz[_to[i]]) tms[_to[i]]=(tms[_to[i]]+tms[now])%p;

            if(!deg[_to[i]]) Q.push(_to[i]);

        }

        for(LL i=_top[now];i;i=_nex[i]) vis[_to[i]]=false;

    }

}

int main()

{

    n=read(),m=read(),p=read();

    while(m--)

    {

        LL x=read(),y=read();

        to[++cnt]=y,nex[cnt]=top[x],top[x]=cnt;

    }

    for(LL i=1;i<=n;i++) if(!dfn[i]) tarjan(i);

    for(LL i=1;i<=n;i++)

        for(LL j=top[i];j;j=nex[j])

            if(bel[i]!=bel[to[j]])

            {

                if(SS.find(make_pair(bel[i],bel[to[j]]))!=SS.end()) continue;

                _to[++_cnt]=bel[to[j]],_nex[_cnt]=_top[bel[i]],_top[bel[i]]=_cnt,deg[bel[to[j]]]++;

                SS.insert(make_pair(bel[i],bel[to[j]]));

            }

    work();

    for(LL i=1;i<=js;i++)

        if(ans1<val[i]) ans1=val[i],ans2=tms[i];

        else if(ans1==val[i]) ans2=(ans2+tms[i])%p;

    printf("%lld\n%lld",ans1,ans2);

    return 0;

}

巴特西

Luogu P2272 [ZJOI2007]最大半连通子图(Tarjan+dp)

题意