Pagini recente » Cod sursa (job #2580809) | Cod sursa (job #370355) | Cod sursa (job #2396619) | Cod sursa (job #2807913) | Cod sursa (job #2272012)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int N = 1e3 + 7;
vector < int > stop, np[N], adia[N], reva[N];
bool viz[N];
int c[N];
int n, nc(0);
void dfs(int nod) {
viz[nod] = 1;
for (auto i : adia[nod])
if (!viz[i])
dfs(i);
stop.push_back(nod);
}
void mk_tps() {
for (int i = 1; i <= n; ++i)
if (!viz[i])
dfs(i);
}
void scd(int nod, int cp) {
viz[nod] = 1;
c[nod] = cp;
np[cp].push_back(nod);
for (auto i : reva[nod])
if (!viz[i])
scd(i, cp);
}
void mk_scc() {
memset(viz, 0, sizeof viz);
for (int i = n - 1; i >= 0; --i)
if (!viz[stop[i]])
scd(stop[i], ++nc);
}
int main()
{
int m, a, b;
cin >> n >> m;
while (m--) {
cin >> a >> b;
adia[a].push_back(b);
reva[b].push_back(a);
}
mk_tps();
mk_scc();
cout << nc << '\n';
for (int i = 1; i <= nc; ++i) {
for (auto p : np[i])
cout << p << ' ';
cout << '\n';
}
return 0;
}