Đường đi qua nhiều đảo nhất
View as PDF
Submit solution
Points:
100.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Tại quần đảo ZXY có N hòn đảo, một số hòn đảo đã có cầu nối với nhau, không có chu trình. Từ đảo này ta có thể đi sang đảo khác bằng đường đi trực tiếp hoặc đi gián tiếp qua các đảo khác.
Jame vừa đến hòn đảo S, anh muốn đi bằng đường bộ đến các đảo khác. Khi đến một đảo, anh ấy có thể nghỉ ngơi ở đảo ấy hoặc đi tiếp sang các đảo khác. Tất nhiên, anh ấy chỉ muốn tham quan mỗi đảo một lần.
Hãy tìm số đảo nhiều nhất mà Jame có thể tham quan bằng đường bộ.
Dữ liệu vào gồm:
- Dòng 1: Ghi số nguyên dương N, M và S (M, N ≤ 3000, S ≤ N).
- M dòng tiếp theo, mỗi dòng ghi số nguyên dương u và v thể hiện có đường đi giữa hai đỉnh u và v (u, v ≤ N).
Kết quả: Ghi ra số đảo nhiều nhất mà Jame có thể tham quan bằng đường bộ.
Ví dụ:
INPUT
12 7 2
1 2
2 5
2 6
6 10
3 4
9 11
9 12
OUTPUT
3
(gồm các đảo 10 6 2)
Comments
i love ame-chan
include<bits/stdc++.h>
using namespace std; int a[3001][3001],m,n,s,gt[3001]; bool visit[3001]; void nhap() { cin>>n>>m>>s; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; a[u][v]=a[v][u]=1; } } void dfs(int u) { visit[u]=false; for(int v=1;v<=n;v++) if (a[u][v]!=0 && visit[v]==true) { gt[v]=gt[u]+1; dfs(v); } } void xuat() { memset(visit,true,sizeof(visit)); memset(gt,0,sizeof(gt)); gt[s]=1; dfs(s); int maxx=0; for (int i=1;i<=n;i++) maxx=max(maxx,gt[i]); //cout<<gt[i]<<" "; cout<<maxx; } int main() { nhap(); xuat(); }