tarjan scc缩点解法

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

typedef long long LL;

const int N=100005;
const int M=600005; // 会建两边图

int n, m, E=0;
int h[N], hs[N];
int dfn[N], low[N], id[N], sz[N], ts=0; // tarjan
bool vis[N];
stack<int> st;
int scc_cnt=0;
int dist[N];

struct Edge{int v, ne, w;}e[M];
inline void add(int h[], int a, int b, int c){
    e[E].v=b;
    e[E].w=c;
    e[E].ne=h[a];
    h[a]=E++;
}

void tarjan(int u){
    dfn[u]=low[u]=++ts;
    st.push(u); vis[u]=true;
    for(int i=h[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u], low[v]);
        }
        else if(vis[v]){
            low[u]=min(low[u], dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        ++scc_cnt;
        int j;
        do{
            j=st.top(); st.pop(); vis[j]=false; 
            id[j]=scc_cnt;
            sz[scc_cnt]++;
        }while(j!=u);
    }
}

int main(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    memset(vis, 0x00, sizeof vis);
    memset(dist, 0x00, sizeof dist);

    // 建立超级源点(xi>=1)
    for(int i=1; i<=n; ++i) add(h, 0, i, 1);
    while(m--){
        int t, a, b;
        cin>>t>>a>>b;
        if(t==1) {add(h, b, a, 0); add(h, a, b, 0);} // xa=xb
        else if(t==2) add(h, a, b, 1); // xa<xb
        else if(t==3) add(h, b, a, 0); // xa>=xb
        else if(t==4) add(h, b, a, 1); // xa>xb
        else if(t==5) add(h, a, b, 0); // xa<=xb
    }
    tarjan(0);
    // 缩点
    bool flag=true;
    for(int i=0; i<=n; ++i){
        for(int j=h[i]; ~j; j=e[j].ne){
            int v=e[j].v;
            int a=id[i], b=id[v];
            if(a==b){ // 如果在一个scc中权值应该为0
                if(e[j].w>0){flag=false; break;}
            }
            else add(hs, a, b, e[j].w);
        }
        if(!flag) break;
    }
    if(!flag) cout<<-1<<endl;
    else{
        for(int i=scc_cnt; i; --i){
            for(int j=hs[i]; ~j; j=e[j].ne){
                int v=e[j].v;
                dist[v]=max(dist[v], dist[i]+e[j].w);
            }
        }
        LL ans=0;
        for(int i=1; i<=scc_cnt; ++i) ans+=(LL)dist[i]*sz[i];
        cout<<ans<<endl;
    }

    return 0;
}