P2272 [ZJOI2007]最大半连通子图

苟！！！！！
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 using namespace std;
  7 const int maxn=100009;
  8 const int maxm=1000009;
  9 int n,m,head[maxn],ecnt,MOD;
 10 int head2[maxn],ecnt2;
 11 struct Edge {
 12     int f,to,nxt;
 13 }ed[maxm],ed2[maxm];
 14 void add_edge(int f,int to,int p)
 15 {
 16     if(p==1)
 17     {
 18         ed[++ecnt].nxt=head[f];
 19         ed[ecnt].f=f;
 20         ed[ecnt].to=to;
 21         head[f]=ecnt;   
 22     }
 23     if(p==2)
 24     {
 25         ed2[++ecnt2].nxt=head2[f];
 26         ed2[ecnt2].to=to;
 27         head2[f]=ecnt2;
 28     }
 29 }
 30 int a[maxn];
 31 void Read()
 32 {
 33     scanf("%d%d%d",&n,&m,&MOD);
 34     for(int i=1,a,b;i<=m;i++)
 35     {
 36         scanf("%d%d",&a,&b);
 37         add_edge(a,b,1);
 38     }
 39 }
 40 int dfn[maxn],low[maxn],tt,tp,stack[maxn],scc_num;
 41 int siz[maxn],co[maxn];
 42 bool vis[maxn];
 43 void tarjan(int x)
 44 {
 45     dfn[x]=low[x]=++tt;
 46     stack[++tp]=x;
 47     vis[x]=1;
 48     for(int i=head[x];i;i=ed[i].nxt)
 49     {
 50         int y=ed[i].to;
 51         if(!dfn[y]) 
 52         {
 53             tarjan(y);
 54             low[x]=min(low[x],low[y]);
 55         }
 56         else if(vis[y]) low[x]=min(low[x],dfn[y]);
 57     }
 58     if(dfn[x]==low[x])
 59     {
 60         scc_num++;
 61         int temp;
 62         do{
 63             temp=stack[tp--];
 64             vis[temp]=0;
 65             co[temp]=scc_num;
 66             siz[scc_num]++;
 67         }while(x!=temp);
 68     }
 69 }
 70 struct ED{
 71     int x,y;
 72 };
 73 bool cmp(Edge a,Edge b)
 74 {
 75     return a.f==b.f?(a.to<b.to):(a.f<b.f);
 76 }
 77 queue <int> q;
 78 int mx;
 79 int rd[maxn],dis[maxn];
 80 int cctv,dp[maxn];
 81 void topsort()
 82 {
 83     memset(dis,-1,sizeof dis);
 84     for(int i=1;i<=scc_num;i++)
 85     {
 86         dp[i]=1;
 87         if(rd[i]==0) q.push(i),dis[i]=siz[i];
 88     }
 89     while(!q.empty())
 90     {
 91         int x=q.front();
 92         q.pop();
 93         for(int i=head2[x];i;i=ed2[i].nxt)
 94         {
 95             int y=ed2[i].to;
 96             int temp=dis[x]+siz[y];
 97             if(temp==dis[y])
 98             {
 99                 dp[y]=(dp[x]+dp[y])%MOD;
100             }
101             if(temp>dis[y]) 
102             {
103                 dis[y]=temp;
104                 dp[y]=dp[x]%MOD;
105             }
106             rd[y]--;
107             if(rd[y]==0) q.push(y);
108         }
109     }
110 }
111 Edge e[maxm];
112 int main()
113 {
114     Read();
115     for(int i=1;i<=n;i++)
116     {
117         if(!dfn[i]) tarjan(i);
118     }  
119     for(int i=1;i<=m;i++)
120     {
121         if(co[ed[i].f]!=co[ed[i].to])
122         {
123             e[++cctv].f=co[ed[i].f];
124             e[cctv].to=co[ed[i].to];
125         }
126     }
127     sort(e+1,e+1+cctv,cmp);
128     for(int i=1;i<=cctv;i++)
129     {
130         if(e[i].f!=e[i-1].f||e[i].to!=e[i-1].to)
131             add_edge(e[i].f,e[i].to,2),rd[e[i].to]++;
132     }
133     topsort();
134     int ans1=0,ans2=0;
135     for(int i=1;i<=scc_num;i++)
136     {
137         if(dis[i]>ans1)
138         {
139             ans1=dis[i];
140             ans2=dp[i];
141         }
142         else
143         if(ans1==dis[i]) 
144         {
145             ans2=(ans2+dp[i])%MOD;
146         }
147     }
148     printf("%d
%d",ans1,ans2);
149 }
tarjan缩点+拓扑（dp）
attention:
步步%；
算dp时，继承上一个点的dp，而不是简单的加一；