Pagini recente » Cod sursa (job #2046973) | Cod sursa (job #2561798) | Cod sursa (job #2210950) | Cod sursa (job #452347) | Cod sursa (job #2928893)
#include <fstream>
#include <vector>
using namespace std;
int n, m;
vector <vector <int>> la, transp;
vector <bool> vis;
vector <int> topo;
vector <vector <int>> res;
vector <int> aux;
void dfs1(int node)
{
vis[node] = true;
for (auto& x : la[node])
if (!vis[x])
dfs1(x);
topo.push_back(node);
}
void dfs2(int node)
{
aux.push_back(node);
vis[node] = true;
for (auto& x : transp[node])
if (!vis[x])
dfs2(x);
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> n >> m;
transp = la = vector<vector<int>>(n, vector<int>());
vis = vector<bool>(n, false);
for (int i = 0; i < m; ++i)
{
int x, y;
fin >> x >> y;
--x; --y;
la[x].push_back(y);
transp[y].push_back(x);
}
fin.close();
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs1(i);
}
}
vis = vector <bool>(n, false);
for (int i = n - 1; i >= 0; --i) {
if (!vis[topo[i]]) {
aux.clear();
dfs2(topo[i]);
res.push_back(aux);
}
}
fout << res.size() << "\n";
for (auto& v : res) {
for (auto& i : v) {
fout << i + 1 << " ";
}
fout << "\n";
}
fout.close();
return 0;
}