Pagini recente » Cod sursa (job #234263) | Cod sursa (job #823834) | Cod sursa (job #1645029) | Cod sursa (job #2405663) | Cod sursa (job #3270171)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, nrctc;
vector<int> g[100005], gt[100005], tout, ctc[100005];
bitset<100005> used;
void dfs1(int node) {
used[node] = true;
for(auto elem : g[node]) {
if(!used[elem]) {
dfs1(elem);
}
}
tout.push_back(node);
}
void dfs2(int node) {
// out << nrctc << ' ' << node << '\n';
used[node] = true;
ctc[nrctc].push_back(node);
for(auto elem : gt[node]) {
if(!used[elem]) {
dfs2(elem);
}
}
}
int main() {
in >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v; in >> u >> v;
g[u].push_back(v);
gt[v].push_back(u);
}
used = 0;
for(int i = 1; i <= n; i++) {
if(!used[i]) {
dfs1(i);
}
}
reverse(tout.begin(), tout.end());
/*
for(auto elem : tout) {
out << elem << ' ';
}
out << '\n';
*/
used = 0;
for(auto elem : tout) {
if(!used[elem]) {
nrctc++;
dfs2(elem);
}
}
out << nrctc << '\n';
for(int i = 1; i <= nrctc; i++) {
sort(ctc[i].begin(), ctc[i].end());
for(auto elem : ctc[i]) {
out << elem << ' ';
}
out << '\n';
}
return 0;
}