Pagini recente » Cod sursa (job #2516418) | Cod sursa (job #1041268) | Cod sursa (job #1705099) | Cod sursa (job #155579) | Cod sursa (job #2340149)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
typedef unsigned int uint;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
class Graph
{
uint V;
/// 0 - normal
/// 1 - transposed
vector<vector<uint>> adj[2];
void DFS(uint node, vector<bool> &v, bool ok, stack<uint> &S);
public:
Graph(uint V);
void Add_edge(uint x, uint y);
void Kosaraju();
};
Graph::Graph(const uint V)
{
this->V = V;
adj[0].assign(V + 1, vector<uint>());
adj[1].assign(V + 1, vector<uint>());
}
void Graph::Add_edge(uint x, uint y)
{
adj[0][x].emplace_back(y);
adj[1][y].emplace_back(x);
}
void Graph::DFS(uint node, vector<bool> &v, bool ok, stack<uint> &S)
{
v[node] = true;
for (auto &i : adj[ok][node])
if (!v[i])
DFS(i,v,ok,S);
S.push(node);
}
void Graph::Kosaraju()
{
stack<uint> S;
vector<bool> v(V + 1, false);
for (uint i = 1; i <= V; ++i)
{
if (!v[i])
DFS(i,v,0,S);
}
vector<stack<uint>> print;
v.clear();
v.assign(V + 1, false);
while (!S.empty())
{
if (!v[S.top()])
{
stack<uint> sol;
DFS(S.top(), v, 1, sol);
print.push_back(sol);
}
S.pop();
}
fout << print.size() << '\n';
for (auto &i : print)
{
while (!i.empty())
{
fout << i.top() << ' ';
i.pop();
}
fout << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
uint n,m;
fin >> n >> m;
Graph G(n);
for (uint x,y,i = 0; i < m; ++i)
{
fin >> x >> y;
G.Add_edge(x,y);
}
G.Kosaraju();
}