Description
一个有向图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的余数。
Input
第一行包含两个整数N，M，X。
N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。
图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。
N ≤100000, M ≤1000000；对于100%的数据， X ≤10^8
Output
应包含两行，第一行包含一个整数K。
第二行包含整数C Mod X.
Sample Input
6 6 20070603 1 2 2 1 1 3 2 4 5 6 6 4
Sample Output
3 3
题解Here!
首先一个强连通缩点，把图变成一个 DAG 。
然后就是求最长链与最长链个数。
求最长链就直接拓扑排序一下。
个数呢？
这个要 DP 一下。
本蒟蒻看到 DP 就不会了。。。
设 f [ i ] 表示图中以 i 为终点的最长链个数，则 f [ i ] 等于与 i 连通并且距离是起点到 i 的最长距离的点的 f 值之和。
附代码：
#include#include #include #include #define MAXN 100010using namespace std;int n,m,p,c=1;int num[MAXN],head[MAXN],indegree[MAXN],vis[MAXN],f[MAXN],g[MAXN];struct Graph{ int next,to;}a[MAXN*10];inline int read(){ int date=0,w=1;char c=0; while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w;}inline void add(int x,int y){ a[c].to=y;a[c].next=head[x];head[x]=c++;}namespace Tarjan{ int c=1,d=1,s=0,top=1; int cstack[MAXN],head[MAXN],deep[MAXN],low[MAXN],colour[MAXN]; bool vis[MAXN]; struct Graph{ int next,to; }edge[MAXN*10]; inline void add_edge(int x,int y){ edge[c].to=y;edge[c].next=head[x];head[x]=c++; } void work(int x){ deep[x]=low[x]=d++; vis[x]=true; cstack[top++]=x; for(int i=head[x];i;i=edge[i].next){ int v=edge[i].to; if(!deep[v]){ work(v); low[x]=min(low[x],low[v]); } else if(vis[v]) low[x]=min(low[x],deep[v]); } if(low[x]==deep[x]){ s++; do{ colour[cstack[top-1]]=s; vis[cstack[top-1]]=false; }while(cstack[--top]!=x); } } void solve(){ int x,y; for(int i=1;i<=m;i++){ x=read();y=read(); add_edge(x,y); } for(int i=1;i<=n;i++)if(!deep[i])work(i); for(int i=1;i<=n;i++)num[colour[i]]++; for(int i=1;i<=n;i++) for(int j=head[i];j;j=edge[j].next){ int v=edge[j].to; if(colour[v]!=colour[i]){ add(colour[i],colour[v]); indegree[colour[v]]++; } } n=s; }}void topsort(){ int u,v; queue q; for(int i=1;i<=n;i++){ if(!indegree[i])q.push(i); f[i]=num[i];g[i]=1; } while(!q.empty()){ u=q.front(); q.pop(); for(int i=head[u];i;i=a[i].next){ v=a[i].to; indegree[v]--; if(!indegree[v])q.push(v); if(vis[v]==u)continue; if(f[u]+num[v]>f[v]){ f[v]=f[u]+num[v]; g[v]=g[u]; } else if(f[u]+num[v]==f[v])g[v]=(g[v]+g[u])%p; vis[v]=u; } }}void work(){ int maxn=0,ans=0; for(int i=1;i<=n;i++){ if(f[i]>maxn){maxn=f[i];ans=g[i];} else if(f[i]==maxn)ans=(ans+g[i])%p; } printf("%d\n%d\n",maxn,ans);}void init(){ n=read();m=read();p=read(); Tarjan::solve(); topsort();}int main(){ init(); work(); return 0;}