Đường đi dài nhất
Xem PDF
Điểm:
1600
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho đồ thị có hướng gồm \(N\) đỉnh và \(M\) cạnh. Các đỉnh được đánh số \(1,2,...,N\) và với mỗi \(i(1\le i\le M)\), cạnh có hướng thứ \(i\) sẽ đi từ đỉnh \(x_i\) đến đỉnh \(y_i\). \(G\) không chứa bất kì chu trình có hướng nào !
Tìm độ dài lớn nhất của đường đi có hướng trong \(G\). Ở đây, độ dài của đường đi có hướng chính là số cạnh trong nó.
Input
-
Dòng thứ nhất chứa \(2\) số nguyên \(N,M(2\le N\le 10^5; 1\le M\le 10^5)\)
-
\(M\) dòng tiếp theo mỗi dòng chứa hai số nguyên \(x_i,y_i(1\le x_i,y_i\le N )\) (Ở đây các cặp \((x_i,y_i)\) phân biệt nhau và đề đảm bảo rằng, \(G\) không chứa bất kì chu trình có hướng nào).
Example
Test 1
Input
3 2
1 2
2 3Output
2Note
Giải thích: Con đường có độ dài lớn nhất là : \(1\rightarrow 2\rightarrow 3\)
Bình luận
include<bits/stdc++.h>
define ll long long
define ld long double
define pb push_back
define pii pair<int, int>
define fi first
define se second
define bit(i, x) ((x >> i) & 1)
define SZ(x) ((int)(x.size()))
define FOR(i, a, b) for (int i = a; i <= b; ++i)
define FORD(i, a, b) for (int i = a; i >= b; --i)
define task "test"
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int MAXn = 3e5 + 7;
const int MOD = 1e9 + 7;
const ll oo = (long long)(1e18);
const int BASE = 3137;
const int BL = 320;
const int INF = (int)1e9;
int n,m,vis[MAXn],id[MAXn],f[MAXn],res,dfstime;
vector<int>adj[MAXn];
stack<int>topo;
void dfs(int u){
vis[u]=1;
for(int v:adj[u]){
if(vis[v]==1){cout<<"BUG";exit(0);}
if(!vis[v]){
dfs(v);
}
}
vis[u]=2;
id[++dfstime]=u;
}
void solution(){
cin>>n>>m;
FOR(i,1,m){
int u,v;cin>>u>>v;
adj[u].pb(v);
}
FOR(i,1,n){
if(!vis[i])dfs(i);
}
FOR(i,1,n){
int u=id[i];
for(int v:adj[u]){
f[u]=max(f[u],f[v]+1);
}
res=max(res,f[u]);
}
cout<<res;
}
int32_t main() {
if (fopen(task".inp", "r")){freopen(task".inp", "r", stdin);freopen(task".out", "w", stdout);}
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ntest = 1; ///cin >> ntest;
while (ntest--) solution();
cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}
Bài này sao không sài dp mình vẫn AC nhỉ 🙁
nói đơn giản lại là tìm cây có độ dài lớn nhất :))
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Có mùi topo =))