結果
問題 | 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;}