Pagini recente » Cod sursa (job #1186454) | Cod sursa (job #2181233) | Cod sursa (job #2537189) | Cod sursa (job #2639725) | Cod sursa (job #1112099)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define foreach(i, v) for (vector<int>::iterator (i) = (v).begin(); (i) != (v).end(); ++(i))
int n, m, nctc = 0;
int s[100005];
vector<int> g[100005], tg[100005], ctc[100005];
bool tr[100005];
void topsort(int nod) {
tr[nod] = true;
foreach(i, g[nod])
if (!tr[*i])
topsort(*i);
s[++s[0]] = nod;
}
void dfs(int nod) {
tr[nod] = true;
foreach(i, tg[nod])
if (!tr[*i])
dfs(*i);
ctc[nctc].push_back(nod);
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
tg[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
if (!tr[i])
topsort(i);
for (int i = 1; i <= n; ++i)
tr[i] = false;
for (int i = n; i >= 1; --i)
if (!tr[s[i]]) {
++nctc;
dfs(s[i]);
}
fout << nctc << '\n';
for (int i = 1; i <= nctc; ++i)
sort(ctc[i].begin(), ctc[i].end());
for (int i = 1; i <= nctc; ++i, fout << '\n')
foreach(j, ctc[i])
fout << *j << ' ';
fin.close();
fout.close();
}