Pagini recente » Borderou de evaluare (job #702918) | Cod sursa (job #2356027) | Cod sursa (job #364257) | Cod sursa (job #2818510) | Cod sursa (job #3248795)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int>> L;
vector<vector<int>> LT;
int n, m;
vector<bool> viz;
stack<int> st;
vector<vector<int>> sol;
int nr_componente_tare_conexe = 0;
void dfs(int node)
{
viz[node] = true;
for (auto v : L[node])
if (!viz[v])
dfs(v);
st.push(node);
}
void dfs_T(int node)
{
viz[node] = true;
for (auto v : LT[node])
if (!viz[v])
dfs_T(v);
sol.back().push_back(node);
}
int main()
{
ifstream f("ctc.in");
f >> n >> m;
viz.resize(n + 1, false);
L.resize(n + 1);
LT.resize(n + 1);
for (int i = 1; i <= m; ++i)
{
int a, b;
f >> a >> b;
L[a].push_back(b);
LT[b].push_back(a);
}
f.close();
for (int i = 1; i <= n; ++i)
if (!viz[i])
dfs(i);
for (int i = 1; i <= n; ++i)
viz[i] = false;
while (!st.empty())
{
int node = st.top();
st.pop();
if (!viz[node])
{
sol.emplace_back();
dfs_T(node);
}
}
std::ofstream g("ctc.out");
g << sol.size() << '\n';
for (auto& comp : sol)
{
for (auto v : comp)
g << v << ' ';
g << '\n';
}
g.close();
return 0;
}