【luogu2272】 [ZJOI2007]最大半连通子图 [tarjan 缩点][拓扑排序]

深藏阁楼爱情的钟 2021-11-17 15:44 216阅读 0赞

[**P2272** \[ZJOI2007\]最大半连通子图][P2272_ _ZJOI2007]

首先缩点 缩完点后存在大量重边 排一遍序去重

然后重新建一个新图 再从入度为0的点一个一个搜 统计并更新答案

感觉过不了多久我再看就看不懂了 一大坨变量![1591261-20190710080504673-81143213.jpg][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define ll long long
     4 const int N=100000+5,M=1000000+5,inf=0x3f3f3f3f;
     5 int n,m,mod,in[N],out[N],cntp[N],dis[N],ans1=0,ans2=0;
     6 int idx=0,Bcnt=0,dfn[N],low[N],bl[N],size[N];
     7 bool inst[N];
     8 stack<int>s;
     9 template<class t>void rd(t &x){
    10     x=0;int w=0;char ch=0;
    11     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    12     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    13     x=w?-x:x;
    14 }
    15 
    16 struct node{
        int u,v;}nod[M];
    17 int head[N],tot=0,cnte=0;
    18 struct edge{
        int u,v,nxt;}e[M];
    19 void add(int u,int v){
    20     e[++tot]=(edge){u,v,head[u]};head[u]=tot;
    21 }
    22 void tarjan(int u){
    23     dfn[u]=low[u]=++idx;
    24     s.push(u),inst[u]=1;
    25     for(int i=head[u],v;i;i=e[i].nxt){
    26         v=e[i].v;
    27         if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
    28         else if(inst[v]&&dfn[v]<low[u]) low[u]=dfn[v];
    29     }
    30     if(low[u]==dfn[u]){
    31         ++Bcnt;
    32         int v;
    33         do{
    34             v=s.top(),s.pop();
    35             bl[v]=Bcnt,++size[Bcnt],inst[v]=0;
    36         }while(u!=v);
    37     }
    38 }
    39 
    40 bool cmp(node a,node b){
        return a.u==b.u?a.v<b.v:a.u<b.u;}
    41 int head2[N],tot2;
    42 struct edge2{
        int v,nxt;}e2[M];
    43 void add2(int u,int v){
    44     e2[++tot2]=(edge2){v,head2[u]};head2[u]=tot2;
    45 }
    46 bool vis[N];
    47 void dfs(int u){
    48     vis[u]=1;
    49     if(!out[u]){
    50         dis[u]=size[u],cntp[u]=1;
    51         ans1=max(ans1,dis[u]);
    52         return;
    53     }
    54     for(int i=head2[u],v;i;i=e2[i].nxt){
    55         v=e2[i].v;
    56         if(!vis[v]) dfs(v);
    57         if(dis[u]<dis[v]+size[u]) dis[u]=dis[v]+size[u],cntp[u]=cntp[v]%mod;
    58         else if(dis[u]==dis[v]+size[u]) cntp[u]=(cntp[u]+cntp[v])%mod;
    59         ans1=max(ans1,dis[u]);
    60     }
    61 }
    62 
    63 int main(){
    64     //freopen("in.txt","r",stdin);
    65     rd(n),rd(m),rd(mod);
    66     for(int i=1,u,v;i<=m;++i) rd(u),rd(v),add(u,v);
    67     memset(dfn,0,sizeof(dfn));
    68     for(int i=1;i<=n;++i)
    69     if(!dfn[i]) tarjan(i);
    70     for(int i=1;i<=tot;++i)
    71     if(bl[e[i].u]!=bl[e[i].v]) nod[++cnte].u=bl[e[i].u],nod[cnte].v=bl[e[i].v];
    72     sort(nod+1,nod+1+cnte,cmp);
    73     for(int i=1;i<=cnte;++i)
    74     if(nod[i].u!=nod[i-1].u||nod[i].v!=nod[i-1].v)
    75     add2(nod[i].u,nod[i].v),++in[nod[i].v],++out[nod[i].u];
    76     for(int i=1;i<=Bcnt;++i)
    77     if(!in[i]&&!vis[i]) dfs(i);
    78     for(int i=1;i<=Bcnt;++i)
    79     if(dis[i]==ans1) ans2=(ans2+cntp[i])%mod;
    80     printf("%d\n%d",ans1,ans2);
    81     return 0;
    82 }

转载于:https://www.cnblogs.com/lxyyyy/p/11159909.html

[P2272_ _ZJOI2007]: https://www.luogu.org/problemnew/show/P2272
[1591261-20190710080504673-81143213.jpg]: /images/20211116/805aa74e01104e48a27602f9eff7c83e.png