头像

xiuzhiyuan

$$\href{https://www.acwing.com/blog/content/14845/}{\Huge\color{blue}{题解主页}}$$




离线:15分钟前


最近来访(1757)
用户头像
罗小呆
用户头像
拉比孝新
用户头像
Eason_Y
用户头像
zhan666nb
用户头像
ACWING-XZY
用户头像
闻天语
用户头像
yxc的小迷妹
用户头像
松月.
用户头像
23计科新生
用户头像
成都队长超人强
用户头像
ohhhdddentist
用户头像
CLUANY
用户头像
Acwer
用户头像
小幽
用户头像
QY琰
用户头像
懸囂轐㷣爥鶩榌
用户头像
有机物
用户头像
od2020
用户头像
perfectionist
用户头像
Finn2009

活动打卡代码 AcWing 456. 车站分级

拓扑排序

#include<iostream>
#include<cstring>
using namespace std;
const int N=2010,M=1000010;
int n,m;
bool stop[N];
int to[M],ne[M],w[M],h[N],idx=1;
int din[N];
int top[N];
int dist[N];
inline void add(int a,int b,int c){
    to[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++,din[b]++;
}
inline void topsort(){
    int hh=1,tt=1;
    for(int i=1;i<=n+m;i++)
        if(!din[i])
            top[tt++]=i;
    while(hh<tt){
        int x=top[hh++];
        for(int i=h[x];i;i=ne[i]){
            int y=to[i];
            if(--din[y]==0)
                top[tt++]=y;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        memset(stop,0,sizeof stop);
        int s,from,to;
        scanf("%d",&s);
        for(int i=1;i<=s;i++){
            int x;
            scanf("%d",&x);
            stop[x]=1;
            if(i==1)
                from=x;
            if(i==s)
                to=x;
        }
        int mid=n+i;
        for(int j=from;j<=to;j++)
            if(stop[j])
                add(mid,j,1);
            else
                add(j,mid,0);
    }
    topsort();
    for(int i=1;i<=n;i++)
        dist[i]=1;
    for(int i=1;i<=n+m;i++){
        int x=top[i];
        for(int j=h[x];j;j=ne[j]){
            int y=to[j];
            dist[y]=max(dist[y],dist[x]+w[j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,dist[i]);
    printf("%d",ans);
    return 0;
}


活动打卡代码 AcWing 396. 矿场搭建

无向图双联通分量

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned long long ULL;
const int N=1010;
int to[N],ne[N],h[N],idx;
int low[N],dft[N],nowt;
int s[N],tt;
int root;
bool ic[N]; //记录该点是否为割点
vector<int> bs[N];
int bcnt;
inline void add(int a,int b){
    to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){
    dft[x]=low[x]=++nowt;
    s[++tt]=x;
    if(!h[x]){
        bcnt++;
        bs[bcnt].push_back(x);
        return;
    }
    int cnt=0;
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dft[x]<=low[y]){
                cnt++;
                if(x!=root||cnt>1)
                    ic[x]=1;
                ++bcnt;
                do{
                    bs[bcnt].push_back(s[tt]);
                }while(s[tt--]!=y);
                bs[bcnt].push_back(x);
            }
        }
        else
            low[x]=min(low[x],dft[y]);
    }
}
int main(){
    int t=0,m;
    while(scanf("%d",&m),m){
        memset(h,0,sizeof h);
        memset(ic,0,sizeof ic);
        memset(dft,0,sizeof dft);
        for(int i=1;i<=bcnt;i++)
            bs[i].clear();
        idx=1;
        nowt=bcnt=0;
        int n=0;
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            n=max(n,a);
            n=max(n,b);
            add(a,b);
            add(b,a);
        }
        for(root=1;root<=n;root++)
            if(!dft[root])
                tarjan(root);
        int ans1=0; //记录最少出口数
        ULL ans2=1; //记录方案数
        for(int i=1;i<=bcnt;i++){
            int cnt=0,len=bs[i].size();
            for(int j=0;j<len;j++)
                if(ic[bs[i][j]])
                    cnt++;
            if(!cnt)
                if(len>1){
                    ans1+=2;
                    ans2*=len*(len-1)/2;
                }
                else
                    ans1++;
            else if(cnt==1){
                ans1++;
                ans2*=len-1;
            }
        }
        printf("Case %d: %d %llu\n",++t,ans1,ans2);
    }
    return 0;
}



题目描述

有n个矿洞和m条边

需要在若干个矿洞建造出口

满足任意一个矿洞坍塌(无法通过坍塌的矿洞或使用坍塌矿洞的出口)

其他矿洞都能到达至少一个出口


基本思路

首先用tarjan算法把图中所有双联通分量缩成点

无向图双联通分量:任意两点间都有两条或以上的点不重复路径

分块.png

这里要作一个特殊定义:两个割点中间连一条边也算一个块

分块2.png

这样的话就会发现,两个相邻的块一定共同拥有一个割点。

答案1

我们把所有的块分成三类

1.没有割点的块

这种块是孤立的

所以需要在块内两个不同节点上建两个出口

(任意一个塌了可以用另外一个)

还要特判一下:如果只有一个点的话建一个出口就行

2.有一个割点的块

比如上图中红色和绿色的块

这种块要在除割点外任意一点建一个出口

这样如果割点塌了,可以用那个出口

如果出口塌了可以通过割点去到别的块

3.有两个或以上割点的块

比如上图中蓝色和黄色的块

这种块是不需要出口的

不难发现,不管哪个点塌了,都可以通过没塌的割点去到别的块

答案2

还是那三类

1.没有割点的块

如果只包含一个节点的话,相当于ans2×1,是没有任何贡献的

否则可以在任意两个点建立出口

答案乘上 点数×(点数-1)÷2

2.有一个割点的块

在除割点外任意一点建出口

答案乘上 点数-1

3.有两个或以上割点的块

这种块不会建任何出口

所以对答案没有贡献

判断一个点是否为割点

每次tarjan都会有一个遍历的初始节点,记为root

可以把一个割点分为是root和不是root两类

不是root的可以直接判断

if(x!=root&&low[y]>=x)

是root的需要开一个cnt记录一下下面有几个块

只有一个的话有可能是这种情况:

割点.png

这样的点并不是割点

两个及以上才算作割点

割点2.png

if(x==root&&cnt>1)

c++代码实现

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned long long ULL;
const int N=1010;
int to[N],ne[N],h[N],idx;   //邻接表的那几个数组和变量
int low[N],dft[N],nowt; //tarjan算法的数组和变量
int s[N],tt;    //tarjan算法中的栈
int root;   //当前遍历的起始节点
bool ic[N]; //记录该点是否为割点
vector<int> bs[N];  //存每个块的所有点
int bcnt;   //块数
inline void add(int a,int b){   //邻接表加边
    to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){ //缩点
    dft[x]=low[x]=++nowt;   //打上标记
    s[++tt]=x;  //入栈
    if(!h[x]){  //孤立的点
        bcnt++;
        bs[bcnt].push_back(x);
        return;
    }
    int cnt=0;  //记录下面有几个块
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){    //还没遍历过
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dft[x]<=low[y]){
                cnt++;
                if(x!=root||cnt>1)
                    ic[x]=1;
                ++bcnt;
                do{ //缩成块
                    bs[bcnt].push_back(s[tt]);
                }while(s[tt--]!=y);
                bs[bcnt].push_back(x);  //x也是块内的点,但不出栈
            }
        }
        else    //遍历过了,是上面的节点
            low[x]=min(low[x],dft[y]);
    }
}
int main(){
    int t=0,m;
    while(scanf("%d",&m),m){
        memset(h,0,sizeof h);
        memset(ic,0,sizeof ic);
        memset(dft,0,sizeof dft);
        for(int i=1;i<=bcnt;i++)
            bs[i].clear();  //初始化数组和vector
        idx=1;
        nowt=bcnt=0;    //初始化变量
        int n=0;
        while(m--){ //加边
            int a,b;
            scanf("%d%d",&a,&b);
            n=max(n,a);
            n=max(n,b); //题目的n要自己算
            add(a,b);
            add(b,a);
        }
        for(root=1;root<=n;root++)  //遍历所有连通块
            if(!dft[root])
                tarjan(root);
        int ans1=0; //记录最少出口数
        ULL ans2=1; //记录方案数
        for(int i=1;i<=bcnt;i++){
            int cnt=0,len=bs[i].size();
            for(int j=0;j<len;j++)  //记录该块中有几个割点
                if(ic[bs[i][j]])
                    cnt++;
            if(!cnt)    //没有割点
                if(len>1){
                    ans1+=2;
                    ans2*=len*(len-1)/2;
                }
                else
                    ans1++;
            else if(cnt==1){    //有一个割点
                ans1++;
                ans2*=len-1;
            }
        }
        printf("Case %d: %d %llu\n",++t,ans1,ans2); //输出答案
    }
    return 0;
}


活动打卡代码 AcWing 1183. 电力

tarjan算法

#include<iostream>
#include<cstring>
using namespace std;
const int N=10010,M=30010;
int to[M],ne[M],h[N],idx;
int low[N],dft[N],nowt;
int root;
int ans,cnt;
inline void add(int a,int b){
    to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){
    low[x]=dft[x]=++nowt;
    int res=0;
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
            res+=low[y]>=dft[x];
        }
        else
            low[x]=min(low[x],dft[y]);
    }
    if(x!=root)
        res++;
    ans=max(ans,res);
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m),n||m){
        idx=1;
        nowt=0;
        memset(h,0,sizeof h);
        memset(dft,0,sizeof dft);
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        ans=cnt=0;
        for(root=0;root<n;root++)
            if(!dft[root]){
                cnt++;
                tarjan(root);
            }
        printf("%d\n",ans+cnt-1);
    }
    return 0;
}


活动打卡代码 AcWing 379. 捉迷藏

二分图的最大匹配

#include<iostream>
#include<cstring>
using namespace std;
const int N=210;
int n,m;
int match[N];
bool way[N][N],vis[N];
bool find(int x){
    for(int i=1;i<=n;i++)
        if(!vis[i]&&way[x][i]){
            vis[i]=1;
            if(!match[i]||find(match[i])){
                match[i]=x;
                return 1;
            }
        }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        way[x][y]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                way[i][j]|=way[i][k]&&way[k][j];
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof vis);
        ans+=find(i);
    }
    printf("%d",n-ans);
    return 0;
}



强连通分量

#include<iostream>
#include<unordered_set>
using namespace std;
typedef long long LL;
const int N=100010,M=2000010;
int to[M],ne[M],h[N],h2[N],idx=1;
int dft[N],low[N],nowt;
int s[N],tt;
bool ins[N];
int block[N],bcnt,num[N];
int f[N],cnt[N];
inline void add(int h[],int a,int b){
    to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x){
    dft[x]=low[x]=++nowt;
    s[++tt]=x;
    ins[x]=1;
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y])
            low[x]=min(low[x],dft[y]);
    }
    if(low[x]==dft[x]){
        ++bcnt;
        do{
            block[s[tt]]=bcnt;
            num[bcnt]++;
            ins[s[tt]]=0;
        }while(s[tt--]!=x);
    }
}
int main(){
    int n,m,mod;
    scanf("%d%d%d",&n,&m,&mod);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(h,a,b);
    }
    for(int i=1;i<=n;i++)
        if(!dft[i])
            tarjan(i);
    unordered_set<LL> he;
    for(int i=1;i<=n;i++)
        for(int j=h[i];j;j=ne[j]){
            int y=to[j];
            LL hash=block[i]*1000000ll+block[y];
            if(block[i]!=block[y]&&!he.count(hash)){
                add(h2,block[i],block[y]);
                he.insert(hash);
            }
        }
    for(int i=bcnt;i;i--){
        if(!f[i]){
            f[i]=num[i];
            cnt[i]=1;
        }
        for(int j=h2[i];j;j=ne[j]){
            int y=to[j];
            if(f[y]<f[i]+num[y]){
                f[y]=f[i]+num[y];
                cnt[y]=cnt[i];
            }
            else if(f[y]==f[i]+num[y])
                cnt[y]=(cnt[y]+cnt[i])%mod;
        }
    }
    int ans1=0,ans2=0;
    for(int i=1;i<=bcnt;i++)
        if(f[i]>ans1){
            ans1=f[i];
            ans2=cnt[i];
        }
        else if(f[i]==ans1)
            ans2=(ans2+cnt[i])%mod;
    printf("%d\n%d",ans1,ans2);
    return 0;
}


活动打卡代码 AcWing 395. 冗余路径

双连通分量

#include<iostream>
using namespace std;
const int N=5010,M=20010;
int to[M],ne[M],h[N],idx=1;
int dft[N],low[N],nowt;
int block[N],bnum;
int s[N],tt;
int cnt[N];
inline void add(int a,int b){
    to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x,int fe){
    dft[x]=low[x]=++nowt;
    s[++tt]=x;
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){
            dfs(y,i);
            low[x]=min(low[x],low[y]);
        }
        else if(i+1>>1!=fe+1>>1)
            low[x]=min(low[x],dft[y]);
    }
    if(low[x]==dft[x]){
        bnum++;
        do
            block[s[tt]]=bnum;
        while(s[tt--]!=x);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++)
        for(int j=h[i];j;j=ne[j]){
            int y=to[j];
            if(block[i]!=block[y])
                cnt[block[y]]++;
        }
    int ans=0;
    for(int i=1;i<=bnum;i++)
        if(cnt[i]==1)
            ans++;
    printf("%d",ans+1>>1);
    return 0;
}


活动打卡代码 AcWing 368. 银河

缩点

#include<iostream>
using namespace std;
const int N=100010,M=600010;
typedef long long LL;
int to[M],ne[M],w[M],h[N],idx=1;
int h2[N];
int dft[N],low[N],nowt;
int s[N],tt;
bool ins[N];
int block[N],bnum;
int dist[N],num[N];
inline void add(int h[],int a,int b,int c){
    to[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x){
    dft[x]=low[x]=++nowt;
    ins[x]=1;
    s[++tt]=x;
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y])
            low[x]=min(low[x],dft[y]);
    }
    if(low[x]==dft[x]){
        ++bnum;
        do{
            ins[s[tt]]=0;
            block[s[tt]]=bnum;
            num[bnum]++;
        }while(s[tt--]!=x);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        add(h,0,i,1);
    while(m--){
        int type,a,b;
        scanf("%d%d%d",&type,&a,&b);
        if(type==1){
            add(h,a,b,0);
            add(h,b,a,0);
        }
        else if(type==2)
            add(h,a,b,1);
        else if(type==3)
            add(h,b,a,0);
        else if(type==4)
            add(h,b,a,1);
        else
            add(h,a,b,0);
    }
    dfs(0);
    bool flag=1;
    for(int i=0;i<=n;i++){
        for(int j=h[i];j;j=ne[j]){
            int y=to[j];
            if(block[i]==block[y]&&w[j]>0){
                flag=0;
                break;
            }
            add(h2,block[i],block[y],w[j]);
        }
        if(!flag)
            break;
    }
    if(!flag)
        printf("-1");
    else{
        for(int i=bnum;i;i--){
            for(int j=h2[i];j;j=ne[j]){
                int y=to[j];
                dist[y]=max(dist[y],dist[i]+w[j]);
            }
        }
        LL ans=0;
        for(int i=1;i<=bnum;i++)
            ans+=(LL)dist[i]*num[i];
        printf("%lld",ans);
    }
    return 0;
}


活动打卡代码 AcWing 367. 学校网络

缩点

#include<iostream>
using namespace std;
const int N=110,M=10010;
int to[M],ne[M],h[N],idx=1;
int s[N],tt;
bool ins[N];
int nowt;
int dft[N],low[N];
int block[N],bcnt;
int in[N],out[N];
inline void add(int a,int b){   //邻接表加边
    to[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x){    //缩点
    s[++tt]=x;
    ins[x]=1;
    dft[x]=low[x]=++nowt;
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y])
            low[x]=min(low[x],dft[y]);
    }
    if(low[x]==dft[x]){
        ++bcnt;
        do{
            block[s[tt]]=bcnt;
            ins[s[tt]]=0;
        }while(s[tt--]!=x);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        while(scanf("%d",&x),x)
            add(i,x);
    }
    for(int i=1;i<=n;i++)
        if(!dft[i])
            dfs(i);
    for(int i=1;i<=n;i++)
        for(int j=h[i];j;j=ne[j]){
            int a=block[i],b=block[to[j]];
            if(a!=b){
                in[b]++;
                out[a]++;
            }
        }
    int scnt=0,tcnt=0;
    for(int i=1;i<=bcnt;i++){   //记录没有入边的块和没有出边的块
        if(!in[i])
            scnt++;
        if(!out[i])
            tcnt++;
    }
    printf("%d\n",scnt);
    if(bcnt==1)
        printf("%d",0);
    else
        printf("%d",max(scnt,tcnt));
    return 0;
}


活动打卡代码 AcWing 1174. 受欢迎的牛

缩点

#include<iostream>
using namespace std;
const int N=10010,M=50010;
int to[M],ne[M],h[N],idx=1;
int to2[M],ne2[M],h2[N];
int dft[N],low[N];
bool vis[N];
int nowt;
int s[N],tt;
bool ins[N];
int fa[N],num[N];
bool ho[N];
inline int find(int x){
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
inline void pt(int x,int y){
    int a=find(x),b=find(y);
    if(a==b)
        return;
    num[a]+=num[b];
    fa[b]=a;
}
inline void add(int a,int b){
    to[idx]=b,ne[idx]=h[a],h[a]=idx;
    to2[idx]=a,ne2[idx]=h2[b],h2[b]=idx++;
}
void dfs1(int x){
    s[++tt]=x,ins[x]=1;
    dft[x]=low[x]=++nowt;
    for(int i=h[x];i;i=ne[i]){
        int y=to[i];
        if(!dft[y]){
            dfs1(y);
            low[x]=min(low[x],low[y]);
        }
        else if(ins[y])
            low[x]=min(low[x],dft[y]);
    }
    if(low[x]==dft[x])
        do{
            ins[s[tt]]=0;
            pt(x,s[tt]);
        }while(s[tt--]!=x);
}
void dfs2(int x){
    vis[x]=1;
    for(int i=h2[x];i;i=ne2[i]){
        int y=to2[i];
        if(!vis[y])
            dfs2(y);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        num[i]=1;
    }
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=n;i++)
        if(!dft[i])
            dfs1(i);
    for(int i=1;i<idx;i++){
        int a=find(to2[i]),b=find(to[i]);
        if(a!=b)
            ho[a]=1;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int a=find(i);
        if(!ho[a]){
            if(ans&&ans!=a){
                printf("0");
                return 0;
            }
            ans=a;
        }
    }
    dfs2(ans);
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            printf("0");
            return 0;
        }
    printf("%d",num[ans]);
    return 0;
}