- const int maxn = 100;
- vector<int> G[maxn];
- int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
- stack<int> S;
- void dfs(int u) {
- pre[u] = lowlink[u] = ++dfs_clock;
- S.push(u);
- for(int i = 0; i <G[u].size(); i++){
- int v = G[u][i];
- if(!pre[v]) {
- dfs(v);
- lowlink[u] = min(lowlink[u], lowlink[v]);
- } else if(!sccno[v]) {
- lowlink[u] = min(lowlink[u], pre[v]);
- }
- }
- if(lowlink[u] == pre[u]){
- scc_cnt++;
- for(;;) {
- int x = S.top();S.pop();
- sccno[x] = scc_cnt;
- if(x == u) break;
- }
- }
- }
- void find_scc(int n) {
- dfs_clock = scc_cnt = 0;
- memset(sccno, 0, sizeof(sccno));
- memset(pre, 0, sizeof(pre));
- for(int i = 0; i < n; i++){
- if(!pre[i]) dfs(i);
- }
- }
模板题 (HDU-1269)
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 10000 + 5, inf = 1e8;
- vector<int> G[maxn];
- int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
- stack<int> S;
- void dfs(int u) {
- pre[u] = lowlink[u] = ++dfs_clock;
- S.push(u);
- for(int i = 0; i < G[u].size(); i++){
- int v = G[u][i];
- if(!pre[v]) {
- dfs(v);
- lowlink[u] = min(lowlink[u], lowlink[v]);
- } else if(!sccno[v]) {
- lowlink[u] = min(lowlink[u], pre[v]);
- }
- }
- if(lowlink[u] == pre[u]){
- scc_cnt++;
- for(;;) {
- int x = S.top();S.pop();
- sccno[x] = scc_cnt;
- if(x == u) break;
- }
- }
- }
- void find_scc(int n) {
- dfs_clock = scc_cnt = 0;
- memset(sccno, 0, sizeof(sccno));
- memset(pre, 0, sizeof(pre));
- for(int i = 1; i <= n; i++){
- if(!pre[i]) dfs(i);
- }
- }
- int main() {
- int N, M, a, b;
- while(scanf("%d%d", &N, &M) && N != 0){
- for(int i = 1; i <= N; i++) G[i].clear();
- for(int i = 0; i < M; i++) scanf("%d%d", &a, &b),G[a].push_back(b);
- find_scc(N);
- if(scc_cnt == 1) cout<<"Yes\n";
- else cout<<"No\n";
- }
- }
来源: http://www.bubuko.com/infodetail-3100620.html