結果
問題 | No.679 不思議マーケット |
ユーザー |
![]() |
提出日時 | 2018-04-27 23:08:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 1,543 bytes |
コンパイル時間 | 2,227 ms |
コンパイル使用メモリ | 205,708 KB |
最終ジャッジ日時 | 2025-01-05 10:25:29 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include<bits/stdc++.h> using namespace std; struct StronglyConnectedComponents { vector< vector< int > > gg, rg; vector< pair< int, int > > edges; vector< int > comp, order, used; StronglyConnectedComponents(size_t v) : gg(v), rg(v), comp(v, -1), used(v, 0) {} void add_edge(int x, int y) { gg[x].push_back(y); rg[y].push_back(x); edges.emplace_back(x, y); } int operator[](int k) { return (comp[k]); } void dfs(int idx) { if(used[idx]) return; used[idx] = true; for(int to : gg[idx]) dfs(to); order.push_back(idx); } void rdfs(int idx, int cnt) { if(comp[idx] != -1) return; comp[idx] = cnt; for(int to : rg[idx]) rdfs(to, cnt); } int build(int t) { dfs(t); reverse(begin(order), end(order)); int ptr = 0; for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++; return ptr; } }; int N, M; vector< int > g[500]; bool v[500]; int sum; void dfs(int idx, StronglyConnectedComponents &scc) { if(v[idx]) return; v[idx] = true; ++sum; for(auto &to : g[idx]) { scc.add_edge(idx, to); dfs(to, scc); } } int main() { cin >> N >> M; for(int i = 0; i < M; i++) { int t, r; cin >> t >> r; --t; for(int j = 0; j < r; j++) { int x; cin >> x; --x; g[t].emplace_back(x); } } int ret = 0; for(int i = 0; i < N; i++) { memset(v, 0, sizeof(v)); StronglyConnectedComponents scc(N); sum = 0; dfs(i, scc); if(scc.build(i) == sum) ++ret; } cout << ret << endl; }