| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 651973 | ziduo | Potemkin cycle (CEOI15_indcyc) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args)throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
ArrayList<Integer>[] edges = new ArrayList[n];
for(int i=0; i<n; i++)edges[i] = new ArrayList<>();
for(int i=0; i<r; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
edges[a].add(b);
edges[b].add(a);
}
boolean[][] same = new boolean[n][n];
for(int i=0; i<n; i++)for(int j=0; j<edges[i].size(); j++)same[i][edges[i].get(j)]=true;
LinkedList<Integer> list = new LinkedList<>();
for(int i=0; i<n; i++)for(int j: edges[i]) {
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[j]=i;
for(int tar: edges[j])if(!same[tar][i]&&tar!=i) {
list.add(tar);
dist[tar]=j;
}
while(!list.isEmpty()) {
int s= list.size();
for(int k=0; k<s; k++) {
int num = list.removeFirst();
for(int tar: edges[num]) {
if(dist[tar]!=-1||(same[j][tar]&&tar!=i))continue;
dist[tar] = num;
if(tar==i)break;
list.add(tar);
}
if(dist[i]!=-1)break;
}
if(dist[i]!=-1)break;
}
list.clear();
if(dist[i]!=-1) {
int cur = dist[i];
while(cur!=i) {
out.write((cur+1)+" ");
cur = dist[cur];
}
out.write((i+1)+"");
out.flush();
out.close();
return;
}
}
out.write("no");
out.flush();
out.close();
}
}