测评记录

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define OobugoO_ios() ios::sync_with_stdio(false),cin.tie(nullptr)
const int N=2e5+50;
const int M=2e6+50;
//const int mod=998244353;
//const int mod=1e9+7;
//int mod;
const int inf=1e9;
const long long llf=1e18;
const long double PI=acos(-1);
const double eps=1e-7;

vector<pii> G[N];
int cnt,idx,dfn[N],low[N],scc[N],tot[N];
bool in_st[N];
vector<int> st;
void tarjan(int now){
    low[now]=dfn[now]=++cnt;
    st.push_back(now);
    in_st[now]=true;
    for(auto x:G[now]){
        if(dfn[x.first]&&!in_st[x.first])   continue;
        if(!in_st[x.first])
            tarjan(x.first);
        low[now]=min(low[now],low[x.first]);
    }
    if(dfn[now]==low[now]){
        ++idx;
        while(st.back()!=now){
            tot[idx]++;
            in_st[st.back()]=false;
            scc[st.back()]=idx;
            st.pop_back();
        }
        tot[idx]++;
        in_st[now]=false;
        scc[now]=idx;
        st.pop_back();
    }
}

void solve() {
    int  n,m; cin>>n>>m;
    while(m--){
        int f,x,y;
        cin>>f>>x>>y;
        if(f==1){
            G[x].emplace_back(y,0);
            G[y].emplace_back(x,0);
        }else{
            if(f>3) swap(x,y),f-=2;
            if(f==2)
                G[x].emplace_back(y,1);
            else
                G[y].emplace_back(x,0);
        }
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    vector<pii> G_now[N];
    vector<int> deg(idx+1,0);
    for(int i=1;i<=n;i++){
        for(auto x:G[i]){
            if(scc[i]==scc[x.first]&&x.second==-1){
                cout<<"-1\n";
                return;
            }else if(scc[i]!=scc[x.first]){
                G_now[scc[i]].emplace_back(scc[x.first],x.second);
                deg[scc[x.first]]++;
            }
        }
    }
    vector<int> dp(idx+1,0);
    queue<int> q;
    for(int i=1;i<=idx;i++){
        if(!deg[i]){
            q.push(i);
            dp[i]=1;
        }
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(auto x:G_now[now]){
            deg[x.first]--;
            dp[x.first]=max(dp[x.first],dp[now]+x.second);
            if(!deg[x.first])   q.push(x.first);
        }
    }
    ll ans=0;
    for(int i=1;i<=idx;i++){
        ans+=1LL*dp[i]*tot[i];
    }
    cout<<ans<<"\n";
}
signed main() {
    OobugoO_ios();
    int t = 1;  //cin>>t;
    while (t--) solve();
    return 0;
}