Pagini recente » Cod sursa (job #1694272) | Cod sursa (job #2815478) | Cod sursa (job #1720824) | Cod sursa (job #1511405) | Cod sursa (job #1380185)
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
const int MAX_N(100001);
int n, Scc;
std::vector<int> Graph [MAX_N], Transpose [MAX_N], Components [MAX_N];
std::bitset<MAX_N> Mark;
std::stack<int> Stack;
inline void Read (void)
{
std::ifstream input("ctc.in");
int m;
input >> n >> m;
int x, y;
while (m)
{
input >> x >> y;
Graph[x].push_back(y);
Transpose[y].push_back(x);
--m;
}
input.close();
}
inline void Print (void)
{
std::ofstream output("ctc.out");
output << Scc << '\n';
for (int i(1) ; i <= Scc ; ++i)
{
for (unsigned int j(0) ; j < Components[i].size() ; ++j)
output << Components[i][j] << ' ';
output.put('\n');
}
output.close();
}
void Toposort (int node)
{
if (!Mark[node])
{
Mark[node] = true;
for (unsigned int i(0) ; i < Graph[node].size() ; ++i)
Toposort(Graph[node][i]);
Stack.push(node);
}
}
void DepthFirstSearch (int node)
{
if (!Mark[node])
{
Components[Scc].push_back(node);
Mark[node] = true;
for (unsigned int i(0) ; i < Transpose[node].size() ; ++i)
DepthFirstSearch(Transpose[node][i]);
}
}
inline void Kosaraju (void)
{
for (int i(1) ; i <= n ; ++i)
Toposort(i);
Mark.reset();
while (!Stack.empty())
{
if (!Mark[Stack.top()])
{
++Scc;
DepthFirstSearch(Stack.top());
}
Stack.pop();
}
}
int main (void)
{
Read();
Kosaraju();
Print();
return 0;
}