[ZJOI2007]最大半连通子图

题目描述：

给你一个图G，让你求最大半连通子图拥有的节点数K，以及不同的最大半联通子图的数量C，C要对X取模

思路：

这是一个比较复杂的题？

主要思路是：tarjan缩点+拓扑排序+dp

首先使用tarjan缩点，得到一个有向无环图，缩点的时候需要记录每个点集有的点数，

u和v都是缩点后的点，且有u指向v的边，val指的是点集中的点数，f[i] 数组表示从起点出发到 i 的最大半连通子图的数量，

使用拓扑排序，从入度为0的点开始，使用dp，有两种情况：

$dp[u] + val[v] > dp[v]$ ，此时dp[v]的值就可以修改了，dp[v] = dp[u] + val[v], f[v] = f[u]，
dp[u] + val[v] = dp[v], 此时dp[v]的值不需要修改，f[v] += f[u]

此时我们只需要循环缩点后的点集，找出最大的dp值，这就是G的最大半连通子图拥有的节点数K ，对于所有dp = K的点的f数组的值加起来就是不同的最大半连通子图的数目C

有一些小的细节方面：

缩点后建图的时候会建出重边，所以dp的时候要判断一下
记得取模
数组开的要足够大
dp记得初始化

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
//#define inf 0x3f3f3f3f
#define MAX  2000000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, mod;
int x, y;

int tot;//链式前向星建原图
int head[MAX];
struct ran{
    int  to, nex;
}tr[MAX];
void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int tim, cnt;//tim是时间戳，cnt是缩点数
int dfn[MAX], low[MAX];
int val[MAX];//记录每个点集的点的数量
stack<int>st;
int color[MAX];
bool vis[MAX];
void tarjan(int u){//板子
    dfn[u] = low[u] = ++tim;
    vis[u] = 1;
    st.push(u);
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v])low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        int now;
        ++cnt;
        do {
            now = st.top();
            st.pop();
            vis[now] = 0;
            color[now] = cnt;
            ++val[cnt];
        } while (now != u);
    }
}

int ttot;//缩点后的链式前向星
int thead[MAX];
ran ttr[MAX];
void tadd(int u, int v){
    ttr[++ttot].to = v;
    ttr[ttot].nex = thead[u];
    thead[u] = ttot;
}

int maxn;//输出的第一个值
int in[MAX];//点集的入度
int dp[MAX];
int f[MAX];
int pos[MAX];//判断是否是重边

void topo(){
    queue<int>q;
    for(int i = 1; i <= cnt; ++i){
        dp[i] = val[i];//初始化
        f[i] = 1;
        if(!in[i])q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = thead[u]; i; i = ttr[i].nex){
            int v = ttr[i].to;
            --in[v];
            if(!in[v])q.push(v);
            if(pos[v] == u)continue;//判重边
            if(dp[u] + val[v] > dp[v]){
                dp[v] = dp[u] + val[v];
                f[v] = f[u];
            }
            else if(dp[u] + val[v] == dp[v]){
                f[v] = (f[v] + f[u]) % mod;
            }
            pos[v] = u;
        }
    }
    int maxn = 0;
    ll ans = 0;
    for(int i = 1; i <= cnt; ++i)maxn = max(maxn, dp[i]);
    for(int i = 1; i <= cnt; ++i){
        if(dp[i] == maxn)ans = (ans + f[i]) % mod;
    }
    cout<<maxn<<endl<<ans<<endl;
}

int main(){
    sddd(n, m, mod);
    for(int i = 1; i <= m; ++i){
        sdd(x, y);
        add(x, y);
    }
    for(int i = 1; i <= n; ++i){
        if(!dfn[i])tarjan(i);
    }
    for(int u = 1; u <= n; ++u){
        for(int j = head[u]; j; j = tr[j].nex){
            int v = tr[j].to;
            if(color[u] != color[v]){
                ++in[color[v]];
                tadd(color[u], color[v]);
            }
        }
    }
    topo();

    return 0;
}