思路
tarjan的题目
注意是要选出一个点集而不是边集
第一问就是缩点之后最长链，第二问就是有多少个最长链，注意缩点后连边要去重（不然一个链的方案可能会被统计多次）
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <set>
using namespace std;
int scc_cnt,sccno[100100],sccnum[100100],low[100100],dfn[100100],vis[100100],vis2[100100],dp1[100100],dfs_clock,n,m,MOD;
pair<int,int> dp2[100100];
struct Graph{
int u[1001000],v[1001000],fir[1001000],nxt[1001000],cnt=0;
void addedge(int ui,int vi){
++cnt;
u[cnt]=ui;
v[cnt]=vi;
nxt[cnt]=fir[ui];
fir[ui]=cnt;
}
}G1,G2;
stack<int> S;
set<pair<int,int> > S2;
void tarjan(int u){
low[u]=dfn[u]=++dfs_clock;
S.push(u);
vis[u]=true;
for(int i=G1.fir[u];i;i=G1.nxt[i]){
if(!dfn[G1.v[i]]){
tarjan(G1.v[i]);
low[u]=min(low[u],low[G1.v[i]]);
}
else if(vis[G1.v[i]])
low[u]=min(low[u],low[G1.v[i]]);
}
if(dfn[u]==low[u]){
scc_cnt++;
while(1){
int x=S.top();
S.pop();
vis[x]=false;
sccno[x]=scc_cnt;
if(x==u)
break;
}
}
}
void sd(void){
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n;i++){
sccnum[sccno[i]]++;
for(int j=G1.fir[i];j;j=G1.nxt[j]){
int u=sccno[i],v=sccno[G1.v[j]];
if(u>v)
swap(u,v);
if(S2.count(make_pair(u,v)))
continue;
S2.insert(make_pair(u,v));
if(sccno[i]!=sccno[G1.v[j]])
G2.addedge(sccno[i],sccno[G1.v[j]]);
}
}
}
int dfs1(int x){
if(vis[x])
return dp1[x];
vis[x]=true;
for(int i=G2.fir[x];i;i=G2.nxt[i]){
dp1[x]=max(dfs1(G2.v[i]),dp1[x]);
}
dp1[x]+=sccnum[x];
return dp1[x];
}
pair<int,int> dfs2(int x){
if(vis2[x])
return dp2[x];
vis2[x]=true;
dp2[x]=make_pair(0,1);
for(int i=G2.fir[x];i;i=G2.nxt[i]){
pair<int,int> t=dfs2(G2.v[i]);
if(t.first>dp2[x].first){
dp2[x]=t;
}
else if(t.first==dp2[x].first){
dp2[x].second=(dp2[x].second+t.second)%MOD;
}
}
dp2[x].first+=sccnum[x];
return dp2[x];
}
int main(){
scanf("%d %d %d",&n,&m,&MOD);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d %d",&a,&b);
G1.addedge(a,b);
}
sd();
int ans=0,ans2=0;
for(int i=1;i<=scc_cnt;i++)
ans=max(ans,dfs1(i));
for(int i=1;i<=scc_cnt;i++){
pair<int,int> t=dfs2(i);
if(t.first==ans)
ans2=(ans2+t.second)%MOD;
}
printf("%d\n%d\n",ans,ans2);
return 0;
}