Pagini recente » Cod sursa (job #628323) | Cod sursa (job #2326050) | Cod sursa (job #3247101) | Cod sursa (job #3289903) | Cod sursa (job #3274315)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
const int NMAX = 100002;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector <vector <int>> v, inv;
bitset <NMAX> f;
vector <int> topo;
void dfs1(int start) { ///in care fm sortarea
f[start] = 1;
for(auto nod : v[start]) {
if(!f[nod])
dfs1(nod);
}
topo.push_back(start);
}
vector <vector <int>> ctc;
void dfs2(int start) {
f[start] = 1;
for(auto nod : inv[start]) {
if(!f[nod])
dfs2(nod);
}
ctc.back().push_back(start);
}
int main()
{
int n, m;
cin >> n >> m;
v.resize(n + 1);
inv.resize(n + 1);
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
inv[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
if(!f[i])
dfs1(i);
}
f = 0;
for(int i = topo.size() - 1; i >= 0; i--) {
if(!f[topo[i]]) {
ctc.push_back(vector <int>());
dfs2(topo[i]);
}
}
cout << ctc.size() << '\n';
for(int i = 0; i < ctc.size(); i++) {
for(auto var : ctc[i])
cout << var << " ";
cout << '\n';
}
return 0;
}