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

女爷i 2021-11-01 14:12 237阅读 0赞

**很显然的tarjan嘛......拓扑也很容易想到**

**我是不会说我因为懒把拓扑改成DFS结果扔了40分然后就是纯板子了**

**因为我们一条路径的点如果不是一个一个炸，同时炸两个，他们一定会相互到达....**

**找最长链即可。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/Wwb123/p/11329710.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/ac014ddc97564f78ae79d28b112f2802.png