Pagini recente » Cod sursa (job #1588394) | Cod sursa (job #291667) | Cod sursa (job #2611120) | Cod sursa (job #2958199) | Cod sursa (job #3269647)
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <set>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector<set<int>> la, la_t;
queue<vector<int>> componenta_tare_conexa;
stack<int> stiva_kosajaru;
vector<bool> viz;
void Read()
{
f >> n >> m;
la.resize(n + 1);
la_t.resize(n + 1);
viz.resize(n + 1, false);
for (int i = 1; i <= m; i++)
{
int u, v;
f >> u >> v;
la[u].insert(v);
la_t[v].insert(u);
}
}
void DFS(vector<set<int>> &la, int nod_start)
{
viz[nod_start] = true;
for (auto &v : la[nod_start])
{
if (viz[v])
continue;
else
DFS(la, v);
}
// când nodul este finalizat
stiva_kosajaru.push(nod_start);
}
void DFS_kosajaru(vector<set<int>> &la, int nod_start)
{
componenta_tare_conexa.back().push_back(nod_start);
viz[nod_start] = true;
for (auto &v : la[nod_start])
{
if (viz[v])
continue;
else
DFS_kosajaru(la, v);
}
}
int main()
{
Read();
for (int i = 1; i <= n; i++)
{
if (viz[i] == false)
DFS(la, i);
}
viz.assign(n + 1, false);
while (!stiva_kosajaru.empty())
{
int nod = stiva_kosajaru.top();
stiva_kosajaru.pop();
if (viz[nod] == false)
{
componenta_tare_conexa.emplace();
DFS_kosajaru(la_t, nod);
}
}
g << componenta_tare_conexa.size() << '\n';
while (!componenta_tare_conexa.empty())
{
for (auto &v : componenta_tare_conexa.front())
{
g << v << " ";
}
g << '\n';
componenta_tare_conexa.pop();
}
return 0;
}