轰炸行动（bomb） （tarjan缩点和拓扑排序）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<string>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<map>
  9 #include<stack>
 10 #include<queue>
 11 #define MAXN 2001001
 12 #define ps push_back
 13 #define int long long
 14 using namespace std;
 15 struct node{int to,n;}e1[MAXN*2],e2[MAXN*2];
 16 int read()
 17 {
 18     int x=0;char c=getchar();
 19     while(c<‘0‘||c>‘9‘)c=getchar();
 20     while(c>=‘0‘&&c<=‘9‘)
 21     {
 22           x=(x<<1)+(x<<3)+(c^48);
 23           c=getchar();
 24     }
 25     return x;
 26 }
 27 int head1[MAXN],tot1,head2[MAXN],tot2;int sum[MAXN];
 28 vector<int>v[MAXN];
 29 int vis[MAXN],dfn[MAXN],low[MAXN],cnt=0;
 30 void add1(int u,int v)
 31 {
 32     e1[++tot1].to=v;e1[tot1].n=head1[u];head1[u]=tot1;
 33 }
 34 void add2(int u,int v)
 35 {
 36     e2[++tot2].to=v;e2[tot2].n=head2[u];head2[u]=tot2;
 37 }
 38 int n,m;
 39 int de;stack<int>q;int belong[MAXN];int ru[MAXN];
 40 void tarjan(int x)
 41 {
 42     dfn[x]=low[x]=++de;vis[x]=1;q.push(x);
 43     for(int i=head1[x];i;i=e1[i].n)
 44     {
 45         int to=e1[i].to;
 46         if(!dfn[to])
 47         {
 48            tarjan(to);
 49            low[x]=min(low[x],low[to]);
 50         }
 51         else if(vis[to])
 52         {
 53            low[x]=min(low[x],low[to]);
 54         }
 55     }
 56     if(low[x]==dfn[x])
 57     {
 58         cnt++;
 59         int top=0;
 60         do
 61         {
 62             top=q.top();q.pop();
 63             belong[top]=cnt;
 64             vis[top]=0;v[cnt].ps(top);
 65             //printf("cnt=%lld top=%lld\n",cnt,top);
 66         }
 67         while(top!=x);
 68         sum[cnt]=v[cnt].size();
 69     }
 70 }
 71 void init()
 72 {
 73      for(int x=1;x<=n;++x)
 74      {
 75          for(int i=head1[x];i;i=e1[i].n)
 76          {
 77              int to=e1[i].to;
 78              if(belong[x]==belong[to])continue;
 79              add2(belong[x],belong[to]);//单项边
 80              ru[belong[to]]++;
 81              //printf("belong[%lld]=%lld belong[%lld]=%lld\n",x,belong[x],to,belong[to]);
 82          }
 83      }     
 84 }
 85 int deep[MAXN];int maxn=0;
 86 queue<int>qq;
 87 void tuopu()
 88 {
 89      while(!qq.empty())
 90      {
 91            int top=qq.front();
 92            qq.pop();
 93            maxn=max(deep[top],maxn);
 94            for(int i=head2[top];i;i=e2[i].n)
 95            {
 96                int to=e2[i].to;
 97                deep[to]=max(deep[to],deep[top]+sum[to]);
 98                maxn=max(deep[to],maxn);
 99                ru[to]--;
100                if(ru[to]==0)qq.push(to);
101            }
102      }
103 }
104 signed main()
105 {
106     n=read();m=read();
107     for(int i=1;i<=m;++i)
108     {
109         int x,y;
110         x=read();y=read();
111         add1(x,y);
112     }
113     for(int i=1;i<=n;++i)
114     {
115         if(!dfn[i])
116         {
117              tarjan(i);
118         }
119     }
120     init();
121     for(int i=1;i<=cnt;++i)
122     {
123         if(ru[i]==0)
124         {
125             deep[i]=max(deep[i],sum[i]);
126             qq.push(i);
127         }
128     }
129     tuopu();
130     printf("%lld\n",maxn);
131 }