문제 : 백준 16947 서울 지하철 2호선
https://www.acmicpc.net/problem/16947
주어진 그래프에 대해서 임이의 점에서 사이클까지의 거리를 출력하는 문제이다.
풀이
입력이 n개이고 노드의 수가 n개 이므로 정확히 한개의 사이클이 존재한다.
가장 가장자리부터 임이의 노드의 indegree가 1인 노드부터 하나씩 지워나가면 된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
int n, visited[101010];
vector<int> g[101010];
int indeg[101010];
int main(){
scanf(“%d”, &n);
for(int i = 0; i < n; i++){
int u, v; scanf(“%d %d”, &u, &v);
g[u].push_back(v);
g[v].push_back(u);
indeg[u]++;
indeg[v]++;
}
queue<int> q;
for(int i = 1; i <= n; i++){
if(indeg[i] == 1) q.push(i);
}
while(!q.empty()){
int now = q.front();
q.pop();
indeg[now]––;
for(int nx : g[now]){
if(indeg[nx] == 0) continue;
indeg[nx]––;
}
for(int nx : g[now]){
if(indeg[nx] == 1) q.push(nx);
}
}
for(int i = 1; i <= n; i++){
if(indeg[i] == 2){
q.push(i);
visited[i] = true;
}
}
int d = 0, dist[101010] = {};
while(!q.empty()){
int qSize = q.size();
for(int i = 0; i < qSize; i++){
int x = q.front();
q.pop();
dist[x] = d;
for(int nx : g[x]){
if(!visited[nx]){
visited[nx] = true;
q.push(nx);
}
}
}
d++;
}
for(int i = 1; i <= n; i++) printf(“%d “, dist[i]);
}
|
cs |
Leave a Reply
Your email is safe with us.