题意

题目描述

一个有向图(G=(V,E))称为半连通的((Semi-Connected))，如果满足：(forall u,vin V)，满足(u ightarrow v)或(v ightarrow u)，即对于图中任意两点(u,v),存在一条(u)到(v)的有向路径或者从(v)到(u)的有向路径。若(G^prime=(V^prime,E^prime))满足(V^primein 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,3dots N)，保证输入中同一个((a,b))不会出现两次。

输出格式

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

输入输出样例

输入样例#1：

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

输出样例#1：

3
3

说明

对于(100\%)的数据，(Nle 100000,Mle 1000000,Xle 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
%lld",ans1,ans2);
    return 0;
}