Gym 102501K BirdwatchingGym 102501K
題意：題目比較難讀，就是給你一個t點 找到所有 i->t的i點 沒有第二條路徑到達t點。
思路：反向圖 跑dj算法，但是要注意 自環的情況，所有每個點 能夠遍歷多次
代碼：（細節很多）：
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define INF 0x3f3f3f3f3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(a) ((a)&-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i=0;(i)<(n);i++)
#define rep1(i,n) for(int i=1;(i)<=(n);i++)
#define se second
#define MA(a, b) make_pair(a, b)
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef pair
<int,int> pii
;
int dx
[4]= {-1,1,0,0},dy
[4]= {0,0,1,-1};
const ll mod
=10001;
const ll N
=1e5+10;
const double pi
=acos(-1);
const double eps
= 1e-4;
int h
[N
],e
[N
],ne
[N
],idx
;int n
,m
,t
;
vector
<int> b
;
void add(int a
,int b
)
{e
[idx
]=b
,ne
[idx
]=h
[a
];h
[a
]=idx
++;
}
int vis
[N
];
void dj()
{queue
<pii
> q
;for(int i
=h
[t
];i
!=-1;i
=ne
[i
]){q
.push(MA(e
[i
],e
[i
]));}while(q
.size()){int v
=q
.front().fi
;int fa
=q
.front().se
;q
.pop();if(vis
[v
]>=10) continue;if(!vis
[v
]) vis
[v
]=1;else{if(v
!=fa
) vis
[v
]++;else continue;}for(int i
=h
[v
];i
!=-1;i
=ne
[i
]){if(e
[i
]==t
) continue;q
.push(MA(e
[i
],fa
));}}
}int main() {FILL(h
,-1);scanf("%d%d%d",&n
,&m
,&t
);rep1(i
,m
){int u
,v
;scanf("%d%d",&u
,&v
);add(v
,u
);}dj();for(int i
=h
[t
];i
!=-1;i
=ne
[i
]){if(vis
[e
[i
]]==1) b
.push_back(e
[i
]);}printf("%d\n",b
.size());sort(b
.begin(),b
.end());for(int i
=0;i
<b
.size();i
++){printf("%d\n",b
[i
]);}return 0;
}
總結
以上是生活随笔為你收集整理的反向图——dj算法（判断从起点 开始有没有第二条路径能到达）Gym 102501K的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
