Pagini recente » Cod sursa (job #3364751) | Cod sursa (job #3364750)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
using VI = vector<int>;
using VB = vector<bool>;
using VVI = vector<VI>;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
VB v;
set<int> currCmp;
VVI G, GT;
vector<set<int>> ctc;
stack<int> order;
void ReadInput();
void Solve();
void DFS(int node);
void DFST(int node);
int main()
{
ReadInput();
Solve();
return 0;
}
void Solve()
{
for (int node = 1; node <= n; ++node)
if (!v[node])
DFS(node);
v = VB(n + 1);
while (!order.empty())
{
int node = order.top();
order.pop();
if (v[node])
continue;
currCmp.clear();
DFST(node);
ctc.push_back(currCmp);
}
fout << ctc.size() << '\n';
for (auto c : ctc)
{
for (int node : c)
fout << node << ' ';
fout << '\n';
}
}
void DFS(int node)
{
v[node] = true;
for (int nbr : G[node])
if (!v[nbr])
DFS(nbr);
order.push(node);
}
void DFST(int node)
{
v[node] = true;
currCmp.insert(node);
for (int nbr : GT[node])
if (!v[nbr])
DFST(nbr);
}
void ReadInput()
{
fin >> n >> m;
v = VB(n + 1);
G = GT = VVI(n + 1);
int u, v;
while (m--)
{
fin >> u >> v;
G[u].push_back(v);
GT[v].push_back(u);
}
}