This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_A" #include <vector> #include <iostream> #include <algorithm> #include <cassert> #include <set> #include <queue> #include <map> #include <array> using namespace std; #include "../../lib/40-graph/Graph.cpp" #include "../../lib/15-queue/RadixHeap.cpp" #include "../../lib/40-graph/MinimumDirectedClosedCircuit.cpp" int main(){ int N,M; cin >> N >> M; Graph<int> graph(N); for(int i = 0; i < M; ++i){ int u,v; cin >> u >> v; graph.make_edge(u,v,1); } MinimumDirectedClosedCircuit<int> mdcc(graph,1234567); int ans = 0; int inf = 1234567; for(int i = 0; i < N; ++i){ mdcc.solve(i); auto tmp = mdcc.restore(); if(!tmp.empty()) ans = 1; } cout << ans << endl; return 0; }
#line 1 "test/graph/MinimumDirectedClosedCircuit.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_A" #include <vector> #include <iostream> #include <algorithm> #include <cassert> #include <set> #include <queue> #include <map> #include <array> using namespace std; #line 1 "lib/40-graph/Graph.cpp" /* * @title Graph * @docs md/graph/Graph.md */ template<class T> class Graph{ private: const size_t N,H,W; public: vector<vector<pair<size_t,T>>> edges; Graph(const size_t N):H(-1),W(-1),N(N), edges(N) {} Graph(const size_t H, const size_t W):H(H),W(W),N(H*W), edges(H*W) {} inline void make_edge(size_t from, size_t to, T w) { edges[from].emplace_back(to,w); } //{from_y,from_x} -> {to_y,to_x} inline void make_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); } inline void make_bidirectional_edge(size_t from, size_t to, T w) { make_edge(from,to,w); make_edge(to,from,w); } inline void make_bidirectional_edge(pair<size_t,size_t> from, pair<size_t,size_t> to, T w) { make_edge(from.first*W+from.second,to.first*W+to.second,w); make_edge(to.first*W+to.second,from.first*W+from.second,w); } inline size_t size(){return N;} inline size_t idx(pair<size_t,size_t> yx){return yx.first*W+yx.second;} }; #line 1 "lib/15-queue/RadixHeap.cpp" /* * @title RadixHeap - 非負整数heap * @docs md/queue/RadixHeap.md */ template<class T, class Key = unsigned long long> class RadixHeap{ using TypeNode = pair<Key, T>; template<class InnerKey, class ZZ=InnerKey> class Inner{}; template<class InnerKey> class Inner<InnerKey, unsigned long long>{ array<vector<TypeNode>,65> vq; unsigned long long size_num; TypeNode last; inline int bit(unsigned long long a) { return a ? 64 - __builtin_clzll(a) : 0;} public: Inner(T mini) : size_num(0), last(make_pair(0, mini)) {} inline bool empty() { return size_num == 0; } inline size_t size(){ return size_num; } inline void push(TypeNode x){ ++size_num; vq[bit(x.first^last.first)].push_back(x);} inline void emplace(unsigned long long key,T val){ ++size_num; vq[bit(key^last.first)].emplace_back(key,val);} inline TypeNode pop() { if(vq[0].empty()) { int i = 1; while(vq[i].empty()) ++i; last = *min_element(vq[i].begin(),vq[i].end()); for(auto &p : vq[i]) vq[bit(p.first ^ last.first)].push_back(p); vq[i].clear(); } --size_num; auto res = vq[0].back(); vq[0].pop_back(); return res; } }; template<class InnerKey> class Inner<InnerKey, unsigned int>{ array<vector<TypeNode>,33> vq; unsigned int size_num; TypeNode last; inline int bit(unsigned int a) { return a ? 32 - __builtin_clz(a) : 0;} public: Inner(T mini) : size_num(0), last(make_pair(0, mini)) {} inline bool empty() { return size_num == 0; } inline size_t size(){ return size_num; } inline void push(TypeNode x){ ++size_num; vq[bit(x.first^last.first)].push_back(x);} inline void emplace(unsigned int key,T val){ ++size_num; vq[bit(key^last.first)].emplace_back(key,val);} inline TypeNode pop() { if(vq[0].empty()) { int i = 1; while(vq[i].empty()) ++i; last = *min_element(vq[i].begin(),vq[i].end()); for(auto &p : vq[i]) vq[bit(p.first ^ last.first)].push_back(p); vq[i].clear(); } --size_num; auto res = vq[0].back(); vq[0].pop_back(); return res; } }; Inner<Key,Key> inner; public: RadixHeap(T mini) : inner(mini) {} inline bool empty() { return inner.empty();} inline size_t size(){ return inner.size();} inline void push(TypeNode x){ inner.push(x);} inline void emplace(unsigned long long key,T val){ inner.emplace(key,val);} inline TypeNode pop() { return inner.pop(); } }; #line 1 "lib/40-graph/MinimumDirectedClosedCircuit.cpp" /* * @title MinimumDirectedClosedCircuit - 有向グラフの最小閉路検出 * @docs md/graph/MinimumDirectedClosedCircuit.md */ template<class T> class MinimumDirectedClosedCircuit { //Tは整数型のみ static_assert(std::is_integral<T>::value, "template parameter T must be integral type"); Graph<T>& graph; vector<T> dist; vector<int> parent; size_t N; T inf; int last,root; private: T solve_impl() { T mini = inf; last = -1; RadixHeap<int, unsigned int> q(0); q.push({0,root}); dist[root] = 0; while (q.size()) { auto top = q.pop(); size_t curr = top.second; if(top.first > dist[curr]) continue; for(auto& edge:graph.edges[curr]){ size_t next = edge.first; T w = edge.second; if(dist[next] > dist[curr]+w) { dist[next] = dist[curr] + w; parent[next] = curr; q.push({dist[next],next}); } //根に返って来てるなら閉路候補 if(next == root && mini > dist[curr]+w) { mini = dist[curr]+w; last = curr; } } } return mini; } public: MinimumDirectedClosedCircuit(Graph<T>& graph, T inf) : graph(graph),N(graph.size()),dist(graph.size()),parent(graph.size()),inf(inf) { } //rootを含む最小閉路の集合を返す O(NlogN) 閉路がないときは空集合 inline T solve(size_t rt){ root = rt; //初期化 for(int i = 0; i < N; ++i) dist[i] = inf, parent[i] = -1; //最小閉路の大きさを決める T mini = solve_impl(); return mini; } vector<int> restore() { vector<int> res; if(last == -1) return res; int curr = last; res.push_back(curr); while(curr != root) res.push_back(curr = parent[curr]); reverse(res.begin(),res.end()); return res; } }; #line 16 "test/graph/MinimumDirectedClosedCircuit.test.cpp" int main(){ int N,M; cin >> N >> M; Graph<int> graph(N); for(int i = 0; i < M; ++i){ int u,v; cin >> u >> v; graph.make_edge(u,v,1); } MinimumDirectedClosedCircuit<int> mdcc(graph,1234567); int ans = 0; int inf = 1234567; for(int i = 0; i < N; ++i){ mdcc.solve(i); auto tmp = mdcc.restore(); if(!tmp.empty()) ans = 1; } cout << ans << endl; return 0; }