どっかで出てそう?
https://yukicoder.me/problems/no/1813
問題
N個の変数と、M個の条件が与えられる。
各条件では、ある変数が別の変数以上であることが示される。
全変数が同じ値であるようにするには、最低あと何個の条件を加えればよいか。
解法
U番目の変数がV番目の変数以上である、という条件を、有向グラフにおいてU→Vの辺と読み替える。
とすると、全変数が同じ値であるというのは、このグラフを強連結にすることと読み替えられる。
そこでまず元のグラフを強連結成分分解して縮約しまおう。
縮約後のグラフが2個以上の頂点からなる場合、全頂点について入次数・出次数が1以上になればよいので、入次数が0の頂点と出次数が0の頂点の間に辺を張ることにする。
int N,M; class SCC { public: static const int MV = 2025000; vector<vector<int> > SC; int NV,GR[MV]; private: vector<int> E[MV], RE[MV], NUM; int vis[MV]; public: void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}} void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); } void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); } void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu); FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);} void scc() { int c=0,i; SC.clear(); SC.resize(NV); NUM.clear(); assert(NV); FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0; for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){ SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++; } SC.resize(c); } }; vector<int> E[202020]; SCC scc; int in[202020],out[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; scc.init(N); FOR(i,M) { cin>>x>>y; E[x-1].push_back(y-1); scc.add_edge(x-1,y-1); } scc.scc(); FOR(i,N) { FORR(e,E[i]) if(scc.GR[i]!=scc.GR[e]) { in[scc.GR[e]]=1; out[scc.GR[i]]=1; } } if(scc.SC.size()==1) { cout<<0<<endl; } else { int nin=0,nout=0; FOR(i,scc.SC.size()) { if(in[i]==0) nin++; if(out[i]==0) nout++; } cout<<max(nin,nout)<<endl; } }
まとめ
コード量はそこまでおおくないね。