BZOJ1093 [ZJOI2007]最大半连通子图【tarjan缩点 + DAG最长路计数】

题目

　　一个有向图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的余数。

输入格式

　　第一行包含两个整数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

输出格式

　　应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.

输入样例

6 6 20070603

1 2

2 1

1 3

2 4

5 6

6 4

输出样例

题解

一开始被题目吓到了，仔细读题才知道原来就是一个tarjan缩点
最大半连通，其实就是诱导子图中，每对点至少能从其中一个到达另一个。
强联通分量里的点相互到达，缩点。
缩完后是一个DAG图，最大的所求图就是最长的路径了【只有同一条路径长的点满足要求】

要注意的就是统计时要防止由于缩点后新建的重边而重复计算，我用了一个vis数组表示当前点最后被哪个点访问过
具体看代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)

using namespace std;

const int maxn = 100005,maxm = 1000005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int N,M,P,h[maxn],ne = 0,head[maxn],nedge = 0;

struct EDGE{int to,nxt;}ed[maxm],edge[maxm];

inline void build(int u,int v){ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;}

inline void add(int u,int v){edge[nedge] = (EDGE){v,head[u]}; head[u] = nedge++;}

int Scc[maxn],scci = 0,st[maxn],top = 0,low[maxn],dfn[maxn],cnt = 0,Siz[maxn];

void dfs(int u){

    dfn[u] = low[u] = ++cnt;

    st[++top] = u; int to;

    Redge(u){

        if (!dfn[to = ed[k].to]) dfs(to);

        if (dfn[to] && !Scc[to]) low[u] = min(low[u],low[to]);

    }

    if (dfn[u] == low[u]){

        scci++;

        do {Scc[st[top]] = scci; Siz[scci]++;}while (st[top--] != u);

    }

}

void tarjan(){REP(i,N) if (!dfn[i]) dfs(i);}

queue<int> q;

int f[maxn],g[maxn],inde[maxn],vis[maxn];

void solve(){

    memset(head,-1,sizeof(head));

    int u,to;

    REP(i,N){

        u = Scc[i];

        Redge(i) if (Scc[to = ed[k].to] != u) add(u,Scc[to]),inde[Scc[to]]++;

    }

    REP(i,scci) if (!inde[i]) q.push(i),g[i] = 1;

    while (!q.empty()){

        u = q.front(); q.pop();

        f[u] += Siz[u];

        for (int k = head[u]; k != -1; k = edge[k].nxt){

            if (!(--inde[to = edge[k].to])) q.push(to);

            if (vis[to] != u){

                vis[to] = u;

                if (f[to] < f[u]) f[to] = f[u],g[to] = g[u];

                else if (f[to] == f[u]) g[to] = (g[to] + g[u]) % P;

            }

        }

    }

    int ans = 0,gmax = -1;

    REP(i,scci)

        if (f[i] > gmax) {ans = g[i]; gmax = f[i];}

        else if (f[i] == gmax) ans = (ans + g[i]) % P;

    printf("%d\n%d\n",gmax,ans);

}

int main(){

    memset(h,-1,sizeof(h));

    N = RD(); M = RD(); P = RD(); int a,b;

    while (M--) a = RD(),b = RD(),build(a,b);

    tarjan();

    solve();

    return 0;

}

半连通