이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
vector<int> AdjList[1005];
bool visited[1005];
bool AdjMat[1005][1005];
int dist[1005];
int p[1005];
bool forbidden[1005];
int main(){
int N, R;
scanf("%d%d", &N, &R);
memset(AdjMat, 0, sizeof(AdjMat));
for(int i = 0; i < R; i ++){
int a, b;
scanf("%d%d", &a, &b);
AdjList[a].push_back(b);
AdjList[b].push_back(a);
AdjMat[a][b] = 1;
AdjMat[b][a] = 1;
}
memset(visited, 0, sizeof(visited));
for(int i = 0; i < N; i ++){
queue<int> q;
q.push(i);
vector<int> component;
component.push_back(i);
memset(dist, -1, sizeof(dist));
memset(p, -1, sizeof(p));
dist[i] = 0;
int x = -1;
int y = -1;
int minCycle = N+5;
while(!q.empty()){
int u = q.front(); q.pop();
bool found = false;
for(int v: AdjList[u]){
if(dist[v] == -1){
component.push_back(v);
dist[v] = dist[u]+1;
p[v] = u;
q.push(v);
}else if(v != p[u]){
int temp = dist[u]+dist[v] +1 ;
if(temp < minCycle){
minCycle = temp;
//printf("p[%d]=%d; p[%d]=%d\n", u, p[u], v, p[v]);
//found = true;
x = u;
y = v;
}
}
}
if(found){break;}
}
if(minCycle <= N && minCycle >= 4){
//printf("x=%d y=%d\n", x, y);
vector<int> X;
vector<int> Y;
while(x != -1){
X.push_back(x);
x = p[x];
}
reverse(X.begin(), X.end());
memset(forbidden, false, sizeof(forbidden));
for(int x: X){
forbidden[x] = true;
}
/*
memset(dist, -1, sizeof(dist));
memset(p, -1, sizeof(p));
dist[i] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(int v: AdjList[u]){
if(dist[v] == -1 && !forbidden[v]){
component.push_back(v);
dist[v] = dist[u]+1;
p[v] = u;
q.push(v);
}
}
}
*/
while(y != i){
X.push_back(y);
y = p[y];
}
for(int k: X){
printf("%d ", k);
}
return 0;
}
}
printf("no");
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
indcyc.cpp: In function 'int main()':
indcyc.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &R);
~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
# | 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... |
# | 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... |