Pagini recente » Cod sursa (job #1246529) | Cod sursa (job #2924612) | Cod sursa (job #1898681) | Cod sursa (job #2286441) | Cod sursa (job #2920450)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
fstream cin("ctc.in", ios::in), cout("ctc.out", ios::out);
vector<vector<int>> v, vt;
vector<set<int>> sol;
vector<int> f;
stack<int> s;
int n, m, componente;
void dfs(int nod)
{
f[nod] = 1;
for (int next_nod : v[nod])
{
if (!f[next_nod])
{
dfs(next_nod);
}
}
s.push(nod);
}
void dfst(int nod)
{
f[nod] = 2;
sol[componente - 1].insert(nod);
for (int next_nod : vt[nod])
{
if (f[next_nod] == 1)
{
dfst(next_nod);
}
}
}
void kosaraju()
{
f.resize(n + 1, 0);
for (int i = 1; i <= n; i++)
{
if (!f[i])
{
dfs(i);
}
}
for (; s.size(); s.pop())
{
if (f[s.top()] == 1)
{
componente++;
sol.push_back(set<int>());
dfst(s.top());
}
}
cout << componente << '\n';
for (auto componenta : sol)
{
for(auto x : componenta)
{
cout<<x<<' ';
}
cout<<'\n';
}
}
int main()
{
cin >> n >> m;
v.resize(n + 1);
vt.resize(n + 1);
for (; m; m--)
{
int x, y;
cin >> x >> y;
v[x].push_back(y);
vt[y].push_back(x);
}
kosaraju();
return 0;
}