結果

問題 No.679 不思議マーケット
ユーザー ei1333333
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0