问题描述

LG2272

BZOJ1093


题解

观察半联通的定义,发现图中的一些结点,构成的链一定是一个半联通子图。

此时存在的环可能会干扰求解,于是\(\mathrm{Tarjan}\)缩点。

于是求最长链,过程中计数即可。


\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

const int maxn=100000+7;
const int maxm=1000000+7;
int n,m,mod;

int Head_old[maxn],Next_old[maxm],to_old[maxm],tot_old,u_old[maxm];
int Head_new[maxn],Next_new[maxm],to_new[maxm],tot_new,u_new[maxm];

int size[maxn];

void add_old(int x,int y){
    to_old[++tot_old]=y,Next_old[tot_old]=Head_old[x],Head_old[x]=tot_old,u_old[tot_old]=x;
}

void add_new(int x,int y){
    to_new[++tot_new]=y,Next_new[tot_new]=Head_new[x],Head_new[x]=tot_new,u_new[tot_new]=x;
}

int dfn[maxn],low[maxn],cnt,sta[maxn],ind,top;
bool ins[maxn];

int bel[maxn],rd[maxn],cd[maxn];

void tarjan(int x){//错误笔记:Tarjan没写instack 
    low[x]=dfn[x]=++ind;sta[++top]=x;ins[x]=1;
    for(int i=Head_old[x];i;i=Next_old[i]){
        int y=to_old[i];
        if(dfn[y]){ if(ins[y]) low[x]=min(low[x],dfn[y]);}
        else{
            tarjan(y);low[x]=min(low[x],low[y]);
        }
    }
    if(dfn[x]==low[x]){
        ++cnt;
        while(sta[top]!=x){
            bel[sta[top]]=cnt,ins[sta[top]]=0,top--;size[cnt]++;
        }
        bel[sta[top]]=cnt,top--;size[cnt]++;ins[x]=0;
    }
}

set < pair<int,int> > st;

int que[maxn],rear,fro=1,copyright;
int lft;

bool str[maxn];

void toposort(){
    lft=n;
    for(int i=1;i<=cnt;i++){
        if(!rd[i]) que[++rear]=i,--lft,str[i]=1;
    }
    while(fro<=rear){
        int x=que[fro];++fro;
        for(int i=Head_new[x];i;i=Next_new[i]){
            int y=to_new[i];--rd[y];
            if(!rd[y]) que[++rear]=y,--lft;
        }
    }
}

int cot,length;

bool vis[maxn];
int dep[maxn];
int sum[maxn];

void dfs(int x,int fa){
    if(vis[x]) return;
    vis[x]=1;
    if(!cd[x]){
        dep[x]=size[x];sum[x]=1;return;
    }
    for(int i=Head_new[x];i;i=Next_new[i]){
        int y=to_new[i];
        if(y==fa) continue;
        dfs(y,x);
        if(dep[y]+size[x]>dep[x]) dep[x]=dep[y]+size[x],sum[x]=sum[y]%mod;
        else if(dep[y]+size[x]==dep[x]) sum[x]=(sum[x]+sum[y])%mod;
    }
}

void calc(){
    for(int i=1;i<=cnt;i++){
        if(dep[i]>length){
            length=dep[i];cot=sum[i];
        }
        else if(dep[i]==length){
            cot=(cot+sum[i])%mod;
        }
    }
}

void debug_rebuild(){
    puts("function debug_rebuild");
    printf("Node number : %d\n",cnt);
    printf("Edge number : %d\n",tot_new);
    for(int i=1;i<=tot_new;i++){
        printf("Edge %d u:%d v:%d\n",i,u_new[i],to_new[i]);
    }
    puts("\nbelong:");
    for(register int i=1;i<=n;i++){
        printf("Node %d belong to %d\n",i,bel[i]);
    }
}


int main(){
    read(n);read(m);read(mod);
    for(int xx,yy,i=1;i<=m;i++){
        read(xx);read(yy);add_old(xx,yy);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=tot_old;i++){
        int x=bel[u_old[i]],y=bel[to_old[i]];
        if(x==y) continue;
        if(st.count(make_pair(x,y))==1) continue;
        st.insert(make_pair(x,y));add_new(x,y);
        ++rd[y];++cd[x];
    }
    //debug!
/*  puts("");
    puts("********************************************************");
    puts("");
    debug_rebuild();
    puts("");
    puts("********************************************************");
    puts("");*/
    //end debug
    
    
    toposort();
    for(int i=1;i<=cnt;i++){
        if(!vis[i]&&str[i]) dfs(i,0);
    }
    calc();
    printf("%d\n%d\n",length,cot);
    return 0;
}