Đề bài:
Thuật toán:
- BFS từ đỉnh S
- Gọi bac[i] là đồ dài đường đi ngắn nhất từ s đến i
- bac[i] = bac[j] + 1
- với i kề j và j duyệt BFS trước i
- ok[i] = 1 nếu i ổn định, ok[i] = 0 nếu i không ổn định.
- Hãy tham khảo code để biết cách kiểm tra xem i có ổn định không
Code:
- Pascal: http://ideone.com/BGjZip
- C++: http://ideone.com/AQF1wp
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E4+3;
const int oo = 1e9+3;
int n, m, s, u, v, res, bac[MAXN],adj[MAXN][MAXN];
bool ok[MAXN];
queue<int> q;
vector<int> a[MAXN];
int main() {
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n >> m >> s;
FOR(i,1,m) {
cin >> u >> v;
if (!adj[u][v])
a[u].push_back(v);
adj[u][v] = 1;
}
q.push(s); bac[s] = 1;
while (!q.empty()) {
u = q.front();
q.pop();
for(int i=0; i<a[u].size(); i++)
{
v = a[u][i];
if (!bac[v])
{
if (ok[u]) ok[v] = 1;
bac[v] = bac[u] + 1;
q.push(v);
}
else
if (bac[v] == bac[u] + 1) ok[v] = 1;
}
}
FOR(i,1,n) if (ok[i]) res++;
cout << res;
return 0;
} |
const
fi='stable.inp';
fo='stable.out';
maxn=10000;
maxm=50000;
var
link,head,ke : array[1..maxm] of longint;
i,j,n,m,st,ans,s,dau,cuoi,u,v : longint;
q,bac : array[1..maxn] of longint;
ok : array[1..maxn] of boolean;
a : array[1..maxn,1..maxn] of boolean;
procedure push(x : longint);
begin
inc(cuoi);
q[cuoi] := x;
end;
procedure add(i,u,v : longint);
begin
link[i] := head[u];
head[u] := i;
ke[i] := v;
end;
begin
// assign(input,fi);reset(input);
// assign(output,fo);rewrite(output);
read(n,m,s);
for i := 1 to m do
begin
read(u,v);
if a[u,v] = false then
add(i,u,v);
a[u,v] := true;
end;
dau := 1; cuoi := 0;
push(s);
bac[s] := 1;
while (dau <= cuoi) do
begin
u := q[dau];
inc(dau);
i := head[u];
while i <> 0 do
begin
v := ke[i];
if bac[v] = 0 then
begin
if ok[u] then ok[v] := true;
bac[v] := bac[u] + 1;
push(v);
end
else
if bac[v] = bac[u] + 1 then
begin
ok[v] := true;
end;
i := link[i];
end;
end;
for i := 1 to n do
if ok[i] then inc(ans);
writeln(ans);
// close(input);close(output);
end. |
Recent Comments