强联通分量容易出错的地方

这个题强联通分量容易出错的地方我都出了 我把它记下来。。。

 

#include <iostream>

#include <cstdio>

#include <cstring>

#define clr(x) memset(x, 0, sizeof(x))

using namespace std;

 

const int maxn = 50005;

const int maxm = 50005;

 

struct Edge {

       int to, next;

}e[maxm];

int head[maxn], tot;

void add(int u, int v) {

       e[tot].to = v;

       e[tot].next = head[u];

       head[u] = tot++;

}

int min(int a, int b) {

       return a > b ? b : a;

}

int n, m;

int dfn[maxn], low[maxn], id[maxn], outd[maxn], s[maxn], ins[maxn];

int s_cnt, ans_cnt, cnt;

 

 

void init() {

       clr(head);

       clr(dfn); clr(low); clr(id);clr(outd); clr(ins);

       tot = 1;

       s_cnt = 0;

       ans_cnt = 0;

       cnt = 1;

}

 

void dfs(int u) {

       s[s_cnt++] = u;

       ins[u] = 1;

       for(int i = head[u]; i; i = e[i].next) {

              int v = e[i].to;

              if(!dfn[v]) {

                     dfn[v] = low[v] = cnt++;

                     dfs(v);

                     low[u] = min(low[u], low[v]);

              } else if(ins[v]){

                     low[u] = min(low[u], dfn[v]);

              }

       }

       if(dfn[u] == low[u]) {

              ans_cnt++;

              int x;

              do {

                     x = s[--s_cnt];

                     ins[x] = 0;

                     id[x] = ans_cnt;

              } while(x != u);

       }

}

                    

int main() {

       int x, y;

       while(EOF != scanf("%d %d",&n, &m) ) {

              init();

              for(int i = 1; i <= m; i++) {

                     scanf("%d %d",&x, &y);

                     add(x, y);

              }

              for(int i = 1; i <= n; i++) {

                     if(!dfn[i]) {

                            dfn[i] = low[i] = cnt++;

                            dfs(i);

                     }

              }

              if(ans_cnt == 1) {

                     printf("%d\n", n);

                     continue;

              }

              for(int i = 1; i <= n; i++) {

                     for(int j = head[i]; j; j = e[j].next) {

                            int k = e[j].to;

                            if(id[i] != id[k])

                                   outd[id[i]]++;

                     }

              }

              int flag = 0;

              for(int i = 1; i <= ans_cnt; i++) {

                     if(outd[i] == 0) {

                            if(flag == 0) flag = i;

                            else {

                                   flag = 0;

                                   break;

                            }

                     }

              }

              if(flag == 0) {

                     puts("0");

              } else {

                     int sum = 0;

                     for(int i = 1; i <= n; i++) {

                            if(id[i] == flag) {

                                   sum++;

                            }

                     }

                     printf("%d\n", sum);

              }

       }

       return 0;

}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。