1093: [ZJOI2007]最大半连通子图
Time Limit: 30 Sec Memory Limit: 162 MBSubmit: 3766 Solved: 1486
[Submit][Status][Discuss]
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 ≤1
00000, 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
1 2
2 1
1 3
2 4
5 6
6 4
Sample Output
3
3
3
HINT
Source
这道题还是很简单的，不要相信我这调了一个多小时的shabi
tarjin缩完点后，根据拓扑序求出最长链即可
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0;int f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=1e6+10;
struct node{
int y,next,x;
}e[MAXN],E[MAXN];
int linkk[MAXN],Len,Linkk[MAXN],len=0,n,m,MOD,f[MAXN],g[MAXN];
int sum[MAXN],cnt[MAXN],low[MAXN],tot,stark[MAXN],q[MAXN];
int top,head,tail,ine[MAXN],dfn[MAXN],vis[MAXN],dfs_clock=0;
inline void insert(int xx,int yy){
e[++len].y=yy;e[len].next=linkk[xx];linkk[xx]=len;e[len].x=xx;
}
inline void insertt(int xx,int yy){
E[++Len].y=yy;E[Len].next=Linkk[xx];Linkk[xx]=Len;
}
void init(){
n=read();m=read();MOD=read();
for(int i=1;i<=m;i++){
int xx=read();int yy=read();
insert(xx,yy);
}
}
inline void tarjin(int st){
dfn[st]=low[st]=++dfs_clock;
stark[++top]=st;vis[st]=1;
for(int i=linkk[st];i;i=e[i].next){
if(!dfn[e[i].y]){
tarjin(e[i].y);
low[st]=min(low[st],low[e[i].y]);
}
else if(vis[e[i].y]) low[st]=min(low[st],dfn[e[i].y]);
}
if(dfn[st]==low[st]){
tot++;
int k;
do{
k=stark[top--];
ine[k]=tot;
vis[k]=0;
sum[tot]++;
}while(k!=st);
}
}
void solve(){
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjin(i);
}
for(int i=1;i<=len;i++){
if(ine[e[i].x]!=ine[e[i].y]){
insertt(ine[e[i].x],ine[e[i].y]),cnt[ine[e[i].y]]++;
}
}
for(int i=1;i<=tot;i++){
if(!cnt[i]) q[++tail]=i;
f[i]=sum[i];g[i]=1;
}
memset(vis,0,sizeof(vis));
while(head<tail){
int tn=q[++head];
//cout<<tn<<endl;
for(int i=Linkk[tn];i;i=E[i].next){
cnt[E[i].y]--;
if(!cnt[E[i].y]) q[++tail]=E[i].y;
if(tn==vis[E[i].y]) continue;
if(f[tn]+sum[E[i].y]>f[E[i].y]){
f[E[i].y]=f[tn]+sum[E[i].y];
g[E[i].y]=g[tn];
}
else if(f[tn]+sum[E[i].y]==f[E[i].y]){
g[E[i].y]+=g[tn];
g[E[i].y]%=MOD;
}
vis[E[i].y]=tn;
}
}
int maxn=-10000;int sum=0;
for(int i=1;i<=tot;i++){
if(f[i]>maxn){
maxn=f[i];
sum=g[i];
}
else if(f[i]==maxn){
sum=(sum+g[i])%MOD;
}
}
cout<<maxn<<endl;cout<<sum<<endl;
}
int main(){
init();
solve();
return 0;
}