Pagini recente » Cod sursa (job #358095) | Cod sursa (job #496113) | Cod sursa (job #2850380) | Cod sursa (job #849613) | Cod sursa (job #2738626)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<int> g[100005], gt[100005];
vector<int> sorted;
bool v[100005];
vector<vector<int> > ctc;
void dfs1(int x) {
v[x] = true;
for(auto next: g[x])
if(!v[next])
dfs1(next);
sorted.push_back(x);
}
void dfs2(int x) {
v[x] = true;
ctc.back().push_back(x);
for(auto next: gt[x])
if(!v[next])
dfs2(next);
}
int main() {
fin >> n >> m;
while(m--) {
int u, v;
fin >> u >> v;
g[u].push_back(v);
gt[v].push_back(u);
}
for(int i = 1; i <= n; i++)
if(!v[i])
dfs1(i);
for(int i = 1; i <= n; i++) v[i] = false;
for(int i = sorted.size()-1; i >= 0; i--) {
int x = sorted[i];
if(!v[x]) {
ctc.push_back({});
dfs2(x);
}
}
fout << ctc.size() << '\n';
for(auto c: ctc) {
for(auto x: c)
fout << x << ' ';
fout << '\n';
}
}