Advertisement
Guest User

Untitled

a guest
Dec 6th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using std::vector;
  5. using std::cout;
  6. using std::cin;
  7. using std::endl;
  8.  
  9. class Graph
  10. {
  11. protected:
  12.     size_t vertexCount;
  13.     size_t edgeCount;
  14.     bool is_directed_;
  15.  
  16. public:
  17.     typedef size_t  Vertex;
  18.  
  19.     explicit Graph(size_t vertex_count, bool is_directed = false) :
  20.         vertexCount(vertex_count),
  21.         edgeCount(0),
  22.         is_directed_(is_directed) {}
  23.  
  24.     size_t GetVertexCount() const {
  25.         return vertexCount;
  26.     }
  27.     size_t GetEdgeCount() const {
  28.         return edgeCount;
  29.     }
  30.     bool isDirected() const {
  31.         return is_directed_;
  32.     }
  33.     virtual void addEdge(const Vertex& start, const Vertex& finish) {
  34.         edgeCount++;
  35.     }
  36.  
  37.     virtual std::vector<Vertex> GetNeighbors(Vertex v) const = 0;
  38. };
  39.  
  40. class GraphAdjList : public Graph
  41. {
  42. private:
  43.     std::vector<std::vector<Vertex>> adjList;
  44.  
  45. public:
  46.  
  47.     explicit GraphAdjList(size_t vertexCount) :
  48.         Graph(vertexCount), adjList(vertexCount) {}
  49.  
  50.     GraphAdjList(size_t vertexCount, const std::vector<std::vector<Vertex>>& adjMatrix
  51.         , bool is_directed = false) :
  52.         Graph(vertexCount, is_directed)
  53.     {
  54.         adjList = std::vector<std::vector<Vertex>>(vertexCount);
  55.         for (size_t i = 0; i < vertexCount; i++)
  56.         {
  57.             for (size_t j = 0; j < vertexCount; j++)
  58.             {
  59.                 if (adjMatrix[i][j] == 1)
  60.                 {
  61.                     adjList[i].push_back(j);
  62.                     edgeCount++;
  63.                 }
  64.             }
  65.         }
  66.     }
  67.  
  68.     std::vector<Vertex> GetNeighbors(Vertex v) const override
  69.     {
  70.         return adjList[v];
  71.     }
  72.  
  73.     void addEdge(const Vertex& start, const Vertex& finish) override
  74.     {
  75.         if (is_directed_ == 0)
  76.         {
  77.             Graph::addEdge(start, finish);
  78.             adjList[start].push_back(finish);
  79.             adjList[finish].push_back(start);
  80.         }
  81.         else
  82.         {
  83.             Graph::addEdge(start, finish);
  84.             adjList[start].push_back(finish);
  85.         }
  86.     }
  87. };
  88.  
  89. namespace GraphProcessing
  90. {
  91.     typedef size_t Vertex;
  92.     enum VertexMark { WHITE, BLACK, GRAY };
  93.  
  94.     void DFS_Visit(const Graph& graph, Vertex v, std::vector<VertexMark>& color,
  95.         std::vector<Vertex>& component)
  96.     {
  97.         color[v] = GRAY;
  98.         for (const Vertex& u : graph.GetNeighbors(v))
  99.         {
  100.             if (color[u] == WHITE)
  101.             {
  102.                 DFS_Visit(graph, u, color, component);
  103.             }
  104.         }
  105.         component.push_back(v);
  106.         color[v] = BLACK;
  107.     }
  108.  
  109.     std::vector<std::vector<Vertex>> GetSCC(const Graph& graph)
  110.     {
  111.         std::vector<std::vector<Vertex>> SCC_Container;
  112.         std::vector<VertexMark> color(graph.GetVertexCount(), WHITE);
  113.  
  114.         for (Vertex v = 0; v < graph.GetVertexCount(); v++)
  115.         {
  116.             if (color[v] == WHITE)
  117.             {
  118.                 std::vector<Vertex> component(0);
  119.                 DFS_Visit(graph, v, color, component);
  120.                 SCC_Container.push_back(component);
  121.             }
  122.         }
  123.  
  124.         return SCC_Container;
  125.     }
  126.  
  127. }
  128.  
  129. int main()
  130. {
  131.     size_t  vertexNumber, edgeNumber;
  132.     cin >> vertexNumber >> edgeNumber;
  133.  
  134.     GraphAdjList graph(vertexNumber);
  135.     for (size_t i = 0; i < edgeNumber; ++i) {
  136.         Graph::Vertex start, finish;
  137.         cin >> start >> finish;
  138.         graph.addEdge(start - 1, finish - 1);
  139.     }
  140.  
  141.     vector<vector<Graph::Vertex>> SCC = GraphProcessing::GetSCC(graph);
  142.     cout << SCC.size() << endl;
  143.     return 0;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement