This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "https://yukicoder.me/problems/no/1023" #include <vector> #include <iostream> #include <numeric> #include <algorithm> #include <stack> using namespace std; #include "../../lib/41-union-find-tree/UnionFindTree.cpp" #include "../../lib/40-graph/StronglyConnectedComponents.cpp" int main(){ int N,M; cin >> N >> M; vector<pair<int,int>> edge; vector<pair<int,int>> bedge; for(int i = 0; i < M; ++i) { int a,b; cin >> a >> b; a--,b--; int c; cin >> c; if(c==1){ bedge.push_back({a,b}); } else{ edge.push_back({a,b}); } } UnionFindTree uf(N); for(auto& e:bedge){ int a = e.first,b = e.second; if(uf.connected(a,b)){ cout << "Yes" << endl; return 0; } uf.merge(a,b); } StronglyConnectedComponents scc(N); for(auto& e:edge){ int a = e.first,b = e.second; if(uf.connected(a,b)){ cout << "Yes" << endl; return 0; } scc.make_edge(uf[a],uf[b]); } scc.solve(); vector<int> cnt(N,0); for(int i = 0; i < N; ++i) cnt[scc[i]]++; for(int i = 0; i < N; ++i) if(cnt[i] > 1){ cout << "Yes" << endl; return 0; } cout << "No" << endl; return 0; }
#line 1 "test/graph/StronglyConnectedComponents-1.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1023" #include <vector> #include <iostream> #include <numeric> #include <algorithm> #include <stack> using namespace std; #line 1 "lib/41-union-find-tree/UnionFindTree.cpp" /* * @title UnionFindTree - Union Find Tree * @docs md/union-find-tree/UnionFindTree.md */ class UnionFindTree { vector<int> parent,maxi,mini; inline int root(int n) { return (parent[n]<0?n:parent[n] = root(parent[n])); } public: UnionFindTree(const int N = 1) : parent(N,-1),maxi(N),mini(N){ iota(maxi.begin(),maxi.end(),0); iota(mini.begin(),mini.end(),0); } inline bool connected(const int n, const int m) { return root(n) == root(m); } inline void merge(int n,int m) { n = root(n); m = root(m); if (n == m) return; if(parent[n]>parent[m]) swap(n, m); parent[n] += parent[m]; parent[m] = n; maxi[n] = std::max(maxi[n],maxi[m]); mini[n] = std::min(mini[n],mini[m]); } inline int min(const int n) { return mini[root(n)]; } inline int max(const int n) { return maxi[root(n)]; } inline int size(const int n){ return (-parent[root(n)]); } inline int operator[](const int n) { return root(n); } inline void print() { for(int i = 0; i < parent.size(); ++i) cout << root(i) << " "; cout << endl; } }; #line 1 "lib/40-graph/StronglyConnectedComponents.cpp" /* * @title StronglyConnectedComponents - 強連結成分分解 * @docs md/graph/StronglyConnectedComponents.md */ class StronglyConnectedComponents{ int num,is_2sat,half,max_id,cnt; vector<vector<int>> edge; vector<int> label,order,low; stack<size_t> st; inline int rev(int i) { return i < half ? i + half : i - half; } inline void dfs(int& from) { low[from]=order[from]=cnt++; st.push(from); for(int& to:edge[from]) { if(order[to]==-1) { dfs(to); low[from]=min(low[from],low[to]); } else { low[from]=min(low[from],order[to]); } } if (low[from] == order[from]) { while(st.size()) { int u = st.top();st.pop(); order[u] = num; label[u] = max_id; if (u == from) break; } max_id++; } } public: StronglyConnectedComponents(const int n, bool is_2sat=0):num(n),max_id(0),cnt(0),is_2sat(is_2sat){ if(is_2sat) num<<=1; edge.resize(num); label.resize(num); order.resize(num,-1); low.resize(num); half=(num>>1); } inline int operator[](int idx) { return label[idx]; } inline void make_edge(const int from,const int to) { edge[from].push_back(to); } //xがflg_xならばyがflg_y inline void make_condition(int x, bool flg_x, int y, bool flg_y) { if (!flg_x) x = rev(x); if (!flg_y) y = rev(y); make_edge(x, y); make_edge(rev(y), rev(x)); } //is_2sat=1のときに、2satを満たすかを返却する inline bool solve(void) { for (int i = 0; i < num; i++) if (order[i] == -1) dfs(i); for (int& id:label) id = max_id-1-id; if(!is_2sat) return true; for (int i = 0; i < num; ++i) if (label[i] == label[rev(i)]) return false; return true; } vector<vector<int>> topological_sort(void) { vector<vector<int>> ret(max_id); for(int i=0;i<num;++i) ret[label[i]].push_back(i); return ret; } int is_true(int i) { return label[i] > label[rev(i)]; } void print(void) { for(auto id:label) cout << id << " "; cout << endl; } }; #line 11 "test/graph/StronglyConnectedComponents-1.test.cpp" int main(){ int N,M; cin >> N >> M; vector<pair<int,int>> edge; vector<pair<int,int>> bedge; for(int i = 0; i < M; ++i) { int a,b; cin >> a >> b; a--,b--; int c; cin >> c; if(c==1){ bedge.push_back({a,b}); } else{ edge.push_back({a,b}); } } UnionFindTree uf(N); for(auto& e:bedge){ int a = e.first,b = e.second; if(uf.connected(a,b)){ cout << "Yes" << endl; return 0; } uf.merge(a,b); } StronglyConnectedComponents scc(N); for(auto& e:edge){ int a = e.first,b = e.second; if(uf.connected(a,b)){ cout << "Yes" << endl; return 0; } scc.make_edge(uf[a],uf[b]); } scc.solve(); vector<int> cnt(N,0); for(int i = 0; i < N; ++i) cnt[scc[i]]++; for(int i = 0; i < N; ++i) if(cnt[i] > 1){ cout << "Yes" << endl; return 0; } cout << "No" << endl; return 0; }