Hdu 1269 强连通判定

题目链接

 Accepted Code:

 /*************************************************************************

     > File Name: hdu_1269.cpp

     > Author: Stomach_ache

     > Mail: [e-mail]

     > Created Time: 2014年08月06日 星期三 16时26分46秒

     > Propose: hdu 1269

  ************************************************************************/

 //强连通模板题

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 struct SCC {

     vector<int> G[maxn];

     vector<int> rG[maxn];

     vector<int> vs;

     bool used[maxn];

     int cmp[maxn];

     int n, m;

       void init(int n) {

           this->n = n;

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

               G[i].clear();

             rG[i].clear();

         }

         vs.clear();

     }

       void AddEdge(int from, int to) {

           G[from].push_back(to);

         rG[to].push_back(from);

     }

     void dfs(int u) {

           used[u] = true;

           for (int i = ; i < (int)G[u].size(); i++) {

               if (!used[G[u][i]]) dfs(G[u][i]);

         }

         vs.push_back(u);

     }

     void rdfs(int u, int k) {

         cmp[u] = k;

           used[u] = true;

         for (int i = ; i < (int)rG[u].size(); i++) {

               if (!used[rG[u][i]]) rdfs(rG[u][i], k);

         }

     }

     int find_scc() {

           memset(used, false, sizeof(used));

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

               if (!used[i]) dfs(i);

         }

         memset(used, false, sizeof(used));

         int k = ;

         for (int i = (int)vs.size()-; i >= ; i--) {

               if (!used[vs[i]]) rdfs(vs[i], k++);

         }

         return k;

     }

 };

 SCC A;

 int main(void) {

       int n, m;

       while (~scanf("%d %d", &n, &m) && (n || m)) {

           A.init(n);

           while (m--) {

               int a, b;

             scanf("%d %d", &a, &b);

             a--; b--;

             A.AddEdge(a, b);

         }

         int k = A.find_scc();

         if (k == ) puts("Yes");

         else puts("No");

     }

     return ;

 }