Pagini recente » Cod sursa (job #921736) | Cod sursa (job #2290367) | Cod sursa (job #1288149) | Cod sursa (job #521769) | Cod sursa (job #3252944)
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<bool> viz;
void Dfs(int nod, vector<vector<int>>& g, vector<int>& rez)
{
viz[nod] = 1;
for(int i = 0; i < g[nod].size(); i++)
{
int vecin = g[nod][i];
if(viz[vecin] == 0)
{
Dfs(vecin, g, rez);
}
}
rez.push_back(nod);
}
int main()
{
int n, m, i, j, a, b;
vector<vector<int>> g, gt, ctc;
vector<int> sort_t;
in >> n >> m;
viz.resize(n + 1);
g.resize(n + 1);
gt.resize(n + 1);
for(i = 1; i <= m; i++)
{
in >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
}
for(i = 1; i <= n; i++)
{
if(viz[i] == 0)
{
Dfs(i, g, sort_t);
}
}
viz.clear();
viz.resize(n + 1, 0);
for(i = n-1; i >= 0; i--)
{
if(viz[sort_t[i]] == 0)
{
ctc.resize(ctc.size()+1);
Dfs(sort_t[i], gt, ctc.back());
sort(ctc.back().begin(), ctc.back().end());
}
}
out << ctc.size() << '\n';
for(i = 0; i < ctc.size(); i++)
{
for(j = 0; j < ctc[i].size(); j++)
{
out << ctc[i][j] << " ";
}
out << '\n';
}
return 0;
}