题目大意：定义半连通子图为一个诱导子图，其中任意两点(x,y)中x可到达y或y可到达x，求最大半连通子图的大小以及方案数
不就是个缩点之后拓扑序DP求最长链么 这题意逗不逗233333
注意缩点后连边不要连重复了 判重边那里我用了set。。。
#include
#include
#include
#include
#include
#define M 100100 using namespace std; int n,m,p; int ans1,ans2; namespace New_Graph{ struct abcd{ int to,next; }table[1001001]; int head[M],tot; int cnt,size[M]; int len[M],ways[M]; void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } void Topology_DP() { int i,x; for(x=cnt;x;x--) { len[x]=size[x];ways[x]=1; for(i=head[x];i;i=table[i].next) { if(len[table[i].to]+size[x]>len[x]) len[x]=len[table[i].to]+size[x],ways[x]=0; if(len[table[i].to]+size[x]==len[x]) (ways[x]+=ways[table[i].to])%=p; } if(len[x]>ans1) ans1=len[x],ans2=0; if(len[x]==ans1) (ans2+=ways[x])%=p; } } } namespace Old_Graph{ struct abcd{ int to,next; }table[1001001]; int head[M],tot; bool v[M]; int belong[M]; void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } void Tarjan(int x) { static int dpt[M],low[M],T; static int stack[M],top; int i; low[x]=dpt[x]=++T; stack[++top]=x; for(i=head[x];i;i=table[i].next) { if(v[table[i].to]) continue; if(dpt[table[i].to]) low[x]=min(low[x],dpt[table[i].to]); else { Tarjan(table[i].to); low[x]=min(low[x],low[table[i].to]); } } if(dpt[x]==low[x]) { using namespace New_Graph; int t;cnt++; do{ t=stack[top--]; v[t]=1;belong[t]=cnt; size[cnt]++; }while(t!=x); } } } int main() { using namespace Old_Graph; int i,x,y; cin>>n>>m>>p; for(i=1;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y); for(i=1;i<=n;i++) if(!v[i]) Tarjan(i); static set
mark[M]; for(x=1;x<=n;x++) for(i=head[x];i;i=table[i].next) if(belong[table[i].to]!=belong[x]) if(mark[belong[table[i].to]].find(belong[x])==mark[belong[table[i].to]].end()) { New_Graph::Add(belong[table[i].to],belong[x]); mark[belong[table[i].to]].insert(belong[x]); } New_Graph::Topology_DP(); cout<