문제 출처 : https://www.acmicpc.net/problem/16947
16947번: 서울 지하철 2호선
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.
www.acmicpc.net
<C++Code>
|
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
#define max 3001
using namespace std;
vector<int > a[max];
int v[max];
int d[max];
bool visit[max];
int dfs(int x,int pre)
{
if(v[x])
{
return x;
}
v[x]=1;
for(int i=0;i<a[x].size();i++)
{
int y=a[x][i];
if(y==pre) continue;
int re=dfs(y,x);
if(re==-2)
{
return -2;
}
if(re>=0)
{
v[x]=2;
if(x==re)
{
return -2;
}
else
{
return re;
}
}
}
return -1;
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int q,w;
cin>>q>>w;
a[q].push_back(w);
a[w].push_back(q);
}
dfs(1,0);
//for(int i=1;i<=n;i++)
// {
// cout<<v[i]<<' ';
// }
queue<pair<int,int> > q;
for(int i=1;i<=n;i++)
{
if(v[i]==2) continue;
memset(visit,false,sizeof(visit));
int cnt=0;
q.push({1,i});
visit[i]=true;
while(!q.empty())
{
int x=q.front().second;
cnt=q.front().first;
q.pop();
for(int t=0;t<a[x].size();t++)
{
int y=a[x][t];
if(v[y]==2)
{
d[i]=cnt;
break;
}
else if(!visit[y])
{
visit[y]=true;
q.push({cnt+1,y});
}
}
}
}
for(int i=1;i<=n;i++)
{
cout<<d[i]<<' ';
}
return 0;
}
|
cs |
<C++code>
|
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
#define max 3001
using namespace std;
vector<int> a[max];
int dist[max];
bool v[max];
int ans[max];
int dfs(int x,int pre)
{
if(v[x])
{
return x;
}
v[x]=true;
for(int i=0;i<a[x].size();i++)
{
int y=a[x][i];
if(y==pre) continue;
int ans=dfs(y,x);
if(ans==-2)
{
return -2;
}
if(ans>0)
{
dist[y]=2;
if(ans==x)
{
return -2;
}
else
{
return ans;
}
}
}
return -1;
}
int main(void)
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int q,w;
cin>>q>>w;
a[q].push_back(w);
a[w].push_back(q);
}
dfs(1,0);
int cnt=0;
queue<pair<int,int> > q;
bool visit[max];
for(int i=1;i<=n;i++)
{
if(dist[i]==2) continue;
memset(visit,false,sizeof(visit));
while(!q.empty())
{
q.pop();
}
q.push({0,i});
visit[i]=true;
while(!q.empty())
{
int cnt=q.front().first;
int x=q.front().second;
q.pop();
// if(i==6)
// cout<<x<< " ,"<<cnt<<endl;
if(dist[x]==2)
{
ans[i]=cnt;
break;
}
for(int t=0;t<a[x].size();t++)
{
int y=a[x][t];
if(!visit[y])
{
q.push({cnt+1,y});
visit[y]=true;
}
}
}
}
// cout<<endl;
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<' ';
}
return 0;
}
|
cs |
'백준 온라인 저지 > BFS, DFS (그래프)' 카테고리의 다른 글
| 16940번_BFS 스페셜 저지 (1) | 2019.12.15 |
|---|---|
| 16964번_DFS 스페셜 저지 (0) | 2019.12.15 |
| 16929번_Two Dots (DFS) (0) | 2019.12.14 |
| 7562번_나이트의 이동(BFS) (0) | 2019.12.14 |
| 1707번_이분그래프 (0) | 2019.12.14 |