POJ/2186.cc

   1 #include <cstdio>
   2 #include <cstring>
   3 #include <stack>
   4 #include <algorithm>
   5
   6 using std::scanf;
   7 using std::printf;
   8
   9 const int maxn=10001,maxm=50001;
  10
  11 struct
  12 {
  13         int adj,next;
  14 } edge[maxm];
  15
  16 struct
  17 {
  18         int src,dest;
  19 } data[maxm];
  20
  21 int ehead[maxn],dis[maxn],low[maxn],contract[maxn],cnt,tot;
  22 bool instack[maxn];
  23 std::stack<int> stack;
  24
  25 inline void insert_edge(int p, int q)
  26 {
  27         if (p==q) return;
  28         edge[cnt].adj=q;
  29         edge[cnt].next=ehead[p];
  30         ehead[p]=cnt++;
  31 }
  32
  33 void dfs(int i)
  34 {
  35         dis[i]=low[i]=++tot;
  36         stack.push(i);
  37         instack[i]=true;
  38         for (int p=ehead[i]; p!=-1; p=edge[p].next)
  39         {
  40                 int j=edge[p].adj;
  41                 if (!dis[j]) dfs(j);
  42                 if (instack[j]) low[i]=std::min(low[i],low[j]);
  43         }
  44         if (dis[i]==low[i])
  45         {
  46                 int j;
  47                 do
  48                 {
  49                         j=stack.top();
  50                         stack.pop();
  51                         instack[j]=false;
  52                         contract[j]=i;
  53                 } while (j!=i);
  54         }
  55 }
  56
  57 inline void init()
  58 {
  59         std::memset(ehead,255,sizeof(ehead));
  60         cnt=tot=0;
  61 }
  62
  63 int main()
  64 {
  65         init();
  66         int n,m;
  67         scanf("%d%d",&n,&m);
  68         int x,y;
  69         for (int i=1; i<=m; ++i)
  70         {
  71                 std::scanf("%d%d",&data[i].src,&data[i].dest);
  72                 insert_edge(data[i].src,data[i].dest);
  73         }
  74         for (int i=1; i<=n; ++i) if (!dis[i]) dfs(i);
  75         init();
  76         for (int i=1; i<=m; ++i)
  77                 insert_edge(contract[data[i].src],contract[data[i].dest]);
  78         int ans=0;
  79         for (int i=1; i<=n; ++i)
  80                 if (contract[i]==i && ehead[i]==-1)
  81                         if (ans==0) ans=i; else if (ans!=i) ans=-1;
  82         switch (ans)
  83         {
  84                 case -1:
  85                         printf("0\n");
  86                         break;
  87                 case 0:
  88                         printf("%d\n",n);
  89                         break;
  90                 default:
  91                         {
  92                                 int tmp=0;
  93                                 for (int i=1; i<=n; ++i) tmp+=(contract[i]==ans);
  94                                 printf("%d\n",tmp);
  95                                 break;
  96                         }
  97         }
  98         return 0;
  99 }