Submission #58476353

---

Source Code Expand

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
#include <atcoder/modint>
using Modint = atcoder::static_modint<998244353>;
#include <atcoder/scc>
#include <atcoder/dsu>
#include <atcoder/maxflow>
using namespace std;

void testcase(){
    i64 N; cin >> N;
    vector<pair<int,int>> S(N);
    int Z = 26;
    rep(i,N){
        string s; cin >> s;
        S[i] = { s[0] - 'A', s[1] - 'A' };
    }
    auto scc = atcoder::scc_graph(Z);
    rep(i,N) scc.add_edge(S[i].first, S[i].second);
    auto sccs = scc.scc();
    int sccn = int(sccs.size());
    vector<int> scci(Z);
    rep(i,sccn){
        for(int v : sccs[i]) scci[v] = i;
    }
    auto dsu = atcoder::dsu(sccn);
    vector<int> have_edge(sccn);
    auto mf = atcoder::mf_graph<int>(sccn + 2);
    int mf_src = sccn;
    int mf_snk = sccn + 1;
    int ans = 0;
    for(auto [u,v] : S){
        u = scci[u];
        v = scci[v];
        if(u == v) have_edge[u] = 1;
        ans += 1;
        mf.add_edge(u, v, 10000);
        mf.add_edge(mf_src, v, 1);
        mf.add_edge(u, mf_snk, 1);
        dsu.merge(u,v);
    }
    rep(i,sccn) if(dsu.size(i) == 1 && have_edge[i]) ans++;
    ans -= mf.flow(mf_src, mf_snk);
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}

Submission Info

Compile Error

In file included from /opt/ac-library/atcoder/scc:1,
                 from Main.cpp:18:
/opt/ac-library/atcoder/scc.hpp: In member function ‘void atcoder::scc_graph::add_edge(int, int)’:
/opt/ac-library/atcoder/scc.hpp:18:13: warning: unused variable ‘n’ [-Wunused-variable]
   18 |         int n = internal.num_vertices();
      |             ^

Judge Result