题面：[ZJOI2007] 最大半连通子图

题目描述

一个有向图 $G=\left(V,E\right)$ 称为半连通的 (Semi-Connected)，如果满足：$\forall u,v\in V$，满足 $u\to v$ 或 $v\to u$，即对于图中任意两点 $u,v$，存在一条 $u$ 到 $v$ 的有向路径或者从 $v$ 到 $u$ 的有向路径。

若 $G’=\left(V’,E’\right)$ 满足 $V’\subseteq 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$，表示一条有向边 $\left(a,b\right)$。图中的每个点将编号为 $1,2,3\dots N$，保证输入中同一个$\left(a,b\right)$不会出现两次。

输出格式

应包含两行，第一行包含一个整数 $K$，第二行包含整数 $C\bmod X$。

样例 #1

样例输入 #1

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

样例输出 #1

1
2

3
3

提示

对于 $100\%$ 的数据，$N\le 10^5$，$M\le 10^6$，$X\le 10^8$。

思路

首先，我们把题目所谓半连通子图的意思，其实就是这个半连通分量中只要满足任意一对点可达即可，不要求谁到谁。然后我们就发现，强连通分量一定属于半连通分量，并且，强连通变量连接起来构成的一些图，属于半连通分量。

那么对于这个强连通分量连接起来构成的图有什么要求呢？显然是强连通分量缩点后的一条链。为什么？如果不是一条链，也就是说存在分支，他一定会有连接不上的地方，如下图：

所以说，其实就是让我们求出，强连通缩点后，点权和最大的链（点权为该强连通分量的大小）以及数量。

代码的话也就特别好写了。

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int MaxV = 1e5 + 10;
const int MaxE = 1e6 + 10;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, m, P;
pair<int , int > e[MaxE];
Graph< MaxV, MaxE >G;

inline void Input() {
    read(n, m, P);
    for(int i = 1; i <= m; i++) {
        read(e[i].first, e[i].second);
        G.AddEdge(e[i].first, e[i].second);
    }
}

int dfn[MaxV], low[MaxV], cntd;
stack<int >stk; int instk[MaxV];
int cntc, col[MaxV];
vector<int >clb[MaxV];

void Tarjan(int u) {
    dfn[u] = low[u] = ++cntd;
    stk.push(u), instk[u] = 1;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(!dfn[v]) { 
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instk[v]) { 
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        ++cntc;
        int v = stk.top(); stk.pop();
        while(v != u) {
            col[v] = cntc;
            instk[v] = 0;
            clb[cntc].push_back(v);
            v = stk.top(); stk.pop();
        }
        col[v] = cntc;
        instk[v] = 0;
        clb[cntc].push_back(v);
    }
}

int sum[MaxV], inD[MaxV];
ll dp[MaxV];

inline void Init() {
    G.clear();
    for(int i = 1; i <= m; i++) {
        e[i].first = col[e[i].first];
        e[i].second = col[e[i].second];
    }
    sort(e + 1, e + m + 1);
    for(int i = 1; i <= m; i++) {
        if(e[i] == e[i - 1]) continue;
        if(e[i].first == e[i].second) continue;
        G.AddEdge(e[i].first, e[i].second);
        inD[e[i].second]++;
    }
}

inline void TopoSort() {
    queue<int >q;
    for(int i = 1; i <= cntc; i++) {
        if(inD[i] == 0) {
            q.push(i);
            dp[i] = 1, sum[i] = clb[i].size();
        }
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = G.head(u); i; i = G.nt(i)) {
            int v = G.to(i);
            if(sum[u] + clb[v].size() == sum[v]) {
                (dp[v] += dp[u]) %= P;
            }
            else if(sum[u] + clb[v].size() > sum[v]) {
                dp[v] = dp[u];
                sum[v] = sum[u] + clb[v].size();
            }
            if(--inD[v] == 0) {
                q.push(v);
            }
        }
    }
}

inline void Work() {
    for(int i = 1; i <= n; i++) {
        if(dfn[i] == 0) {
            Tarjan(i);
        }
    }
    Init();
    TopoSort();
    ll ans = 0, tot = 0;
    for(int i = 1; i <= cntc; i++) {
        if(ans < sum[i]) {
            ans = sum[i];
            tot = dp[i];
        }
        else if(ans == sum[i]) {
            (tot += dp[i]) %= P;
        }
    }
    printf("%lld\n%lld", ans, tot);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}