Pagini recente » Cod sursa (job #420645) | Cod sursa (job #2298336) | Cod sursa (job #1086747) | Cod sursa (job #1740167) | Cod sursa (job #3149474)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, nr, nr2, viz[100001];
vector<int> G[100001], GT[100001], afis[100001];
stack<int> f;
void dfs(int x) {
viz[x] = 1;
for (int i : G[x])
if (!viz[i])
dfs(i);
f.push(x);
}
void dfs_t(int x) {
viz[x] = 1;
for (int i : GT[x])
if (!viz[i]) {
afis[nr].push_back(i);
dfs_t(i);
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
// Parcurgem G si determinam pt fiecare x nodul final f[x]
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i);
for (int i = 1; i <= n; i++)
viz[i] = 0;
// Pargurgem GT din f[] in ordine descrescatoare
while (!f.empty()) {
int tmp = f.top();
f.pop();
if (!viz[tmp]) {
nr++;
afis[++nr2].push_back(tmp);
dfs_t(tmp);
}
}
fout << nr << "\n";
for (int i = 1; i <= nr; i++) {
for (int tmp : afis[i])
fout << tmp << " ";
fout << "\n";
}
return 0;
}