이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> pii;
const int maxn = 2e5 + 100;
int n;
vector<int> g[maxn];
vector<int> gr[maxn];
int comp[maxn];
int sz[maxn];
vector<int> ord;
int used[maxn];
void dfs(int v){
used[v] = 1;
for(int to: g[v]){
if(!used[to]) dfs(to);
}
ord.push_back(v);
}
void get(int v, int c){
comp[v] = c; sz[c]++;
for(int to: gr[v]){
if(!comp[to]) get(to, c);
}
}
int DFS(int v){
if(used[v]) return 0;
used[v] = 1;
if(sz[comp[v]] > 1) return 1;
for(int to: g[v]){
if(DFS(to)) return 1;
}
return 0;
}
std::variant<bool, std::vector<int>> find_journey(
int N, int M, std::vector<int> U, std::vector<int> V){
n = N;
for(int i = 0; i < M; i++){
int a = U[i] + 1, b = V[i] + 1;
g[a].push_back(b);
gr[b].push_back(a);
}
reverse(ord.begin(), ord.end());
int c = 0;
for(int v: ord){
if(!comp[v]){
c++;
get(v, c);
}
}
fill(used, used + n + 1, 0);
return bool(DFS(1));
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |