結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-03-06 00:56:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 248 ms / 2,000 ms |
コード長 | 1,347 bytes |
コンパイル時間 | 1,000 ms |
コンパイル使用メモリ | 82,028 KB |
最終ジャッジ日時 | 2025-01-19 12:12:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>using namespace std;void dfs(vector<vector<int>> &G, int v, vector<bool> &seen, vector<int> &vlist){seen[v] = true;for(auto u:G[v]){if (seen[u]) continue;dfs(G,u,seen,vlist);}vlist.push_back(v);}vector<int> topological_sort(vector<vector<int>> &G){int V = G.size();vector<bool> seen(V);vector<int> res;for(int v=0; v<V; v++){if (!seen[v]){dfs(G,v,seen,res);}}reverse(res.begin(),res.end());return res;}int main(){int N,M; cin>>N>>M;vector<int> A(N);for(int i=0; i<N; i++) cin>>A[i];vector<vector<int>> G(N);for(int i=0; i<M; i++){int u,v; cin>>u>>v; u--; v--;if (A[u]==A[v]) continue;if (A[u] < A[v]) G[u].push_back(v);else G[v].push_back(u);}int K; cin>>K;vector<bool> lit(N);for(int i=0; i<K; i++){int B; cin>>B;lit[B-1] = true;}auto v = topological_sort(G);vector<int> ans;for(int i=0; i<N; i++){if (lit[v[i]]){ans.push_back(v[i]);for(auto u:G[v[i]]){lit[u] = !lit[u];}}}cout<<ans.size()<<endl;for(auto e:ans){cout<<e+1<<endl;}return 0;}