缩点

· · 个人记录

求强联通分量总结了两个方法： 1.利用并查集思想，每一个强联通分量都是一个并查集，代码如下：


#include<bits/stdc++.h>
using namespace std;
#define N 100010
struct edge{
    int u, v, nxt;
}e[N];
queue <int> q;
int head[N], cnt, n, m, x, y, vis[N], f[N], c[N], s[N], r[N], ans = 1, W[N];
inline void add(int u, int v){
    e[++cnt].u = u;
    e[cnt].v = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
int find(int x){
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
void dfs(int u){
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if(!vis[v]){//如果没搜索
            vis[v] = vis[u] + 1;//记录“深度”
            dfs(v);//继续搜
        }
        int fu = find(u), fv = find(v);
        if(vis[fv] > 0){//一定要是搜索中的
            if(vis[fu] < vis[fv]) f[fv] = fu;
            else f[fu] = fv;//注意这里，深度小的为父亲
        }
    }
    vis[u] = -1;//标记搜索完
    return;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) f[i] = i, scanf("%d",&W[i]);
    for(int i = 1; i <= m; ++i){
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[i])
        {//如果这个点还没搜索就要继续搜
            vis[i] = 1;
            dfs(i);
        }
    }
    for(int i = 1; i <= n; ++i) c[find(i)] += W[i];//缩点权值处理
    memset(head, 0, sizeof(head));
    cnt = 0;
    for(int i = 1; i <= m; ++i){
        x = f[e[i].u], y = f[e[i].v];//由于在上面已经全部遍历过 find 函数了，这里直接调用即可
        if(x != y) add(x, y), r[y]++;//不在一个强连通分量就连边
    }
    for(int i = 1; i <= n; ++i){
        if(i == f[i] && !r[i]) q.push(i), s[i] = c[i];
    }
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].nxt){
            int v = e[i].v;
            s[v] = max(s[v], s[u] + c[v]);
            if(--r[v] == 0) q.push(v);
        }
        ans = max(ans, s[u]);
    }
    cout<<ans;
    return 0;
}

2. tarjan比较麻烦需要重新建图，但是思路清晰，相对而言码量较大，代码如下：

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int from,to,next;
}e[200000];
struct node{
    int from,to,next;
}g[200000];
stack<int> s;
queue<int> q;
int sccnt,cnt,n,m,u,v,tot,ccnt,ans;
int a[100001],pce[100001],head[100001],loop[100001],dfn[100001],low[100001];
int r[100001],cc[100001],vis[200000],color[100001];
void add(int u,int v)
{
    g[++ccnt]=(node){u,v,loop[u]};
    r[v]++;
    loop[u]=ccnt;
}
void Tarjan(int u)
{
    s.push(u);
    vis[u]=1;
    dfn[u]=low[u]=++tot;
    for(int i=head[u] ; i ; i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        int v;
        sccnt++;
        do
        {
            v=s.top();
            pce[sccnt]+=a[v];//把一个强联通分量缩成一个点
            s.pop();
            vis[v]=0;
            color[v]=sccnt;
        }while(u != v);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1 ; i <= n ; i++)
    {
        cin>>a[i];
        cc[i]=-1;
    }
    for(int i=1 ; i <= m ; i++)
    {
        cin>>u>>v;
        e[++cnt]=(edge){u,v,head[u]};
        head[u]=cnt;
    }
    for(int i=1 ; i <= n ; i++)
        if(!dfn[i])Tarjan(i);
    for(int i=1 ; i <= cnt ; i++)
        if(color[e[i].from] != color[e[i].to])
            add(color[e[i].from],color[e[i].to]);
    for(int i=1 ; i <= sccnt ; i++)
        if(!r[i])
        {
            cc[i]=pce[i];
            q.push(i);
        }
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(int i=loop[u] ; i ; i=g[i].next)
        {
            v=g[i].to;
            cc[v]=max(cc[v],cc[u]+pce[v]);
            if(--r[v] == 0)q.push(v);
        }
    }
    for(int i=1 ; i <= sccnt ; i++)ans=max(ans,cc[i]);
    cout<<ans;
    return 0;
}