Pagini recente » Cod sursa (job #2336185) | Cod sursa (job #384380) | Cod sursa (job #2748826) | Cod sursa (job #593671) | Cod sursa (job #2999728)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int DIM = 100001;
int n, m, x, y;
vector<int> d[DIM], t[DIM], sol[DIM];
vector<int> nodes;
int scc[DIM], sccCnt;
bool vis[DIM];
void dfs1(int node) {
vis[node] = true;
for (auto adjNode : d[node])
if (!vis[adjNode])
dfs1(adjNode);
nodes.push_back(node);
}
void dfs2(int node) {
vis[node] = true;
sol[sccCnt].push_back(node);
for (auto adjNode : t[node])
if (!vis[adjNode])
dfs2(adjNode);
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
d[x].push_back(y);
t[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!vis[i])
dfs1(i);
sccCnt = 0;
memset(vis, false, sizeof(vis));
for (auto it = nodes.rbegin(); it != nodes.rend(); it++) {
if (!vis[*it]) {
sccCnt++;
dfs2(*it);
}
}
fout << sccCnt << '\n';
for (int i = 1; i <= sccCnt; i++) {
for (auto node : sol[i])
fout << node << ' ';
fout << '\n';
}
return 0;
}