Pagini recente » Cod sursa (job #3359026) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3359024) | Cod sursa (job #3360763)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int nmax = 100'000;
bool viz[nmax];
void dfs(int node, vector<int> *adj, vector<int> &ans) {
viz[node] = true;
for(auto i : adj[node])
if(!viz[i]) dfs(i, adj, ans);
ans.pb(node);
}
vector<int> adj[nmax];
vector<int> radj[nmax];
vector<int> topo;
vector<int> ctc[nmax];
int main() {
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m; cin >> n >> m;
topo.reserve(n);
for(int u, v; m --;) {
cin >> u >> v; u --; v --;
adj[u].pb(v); radj[v].pb(u);
}
for(int i = 0; i < n; i ++) {
if(!viz[i])
dfs(i, adj, topo);
}
memset(viz, 0, sizeof(bool) * n);
reverse(topo.begin(), topo.end());
int cnt = 0;
for(auto i : topo) {
if(!viz[i])
dfs(i, radj, ctc[cnt ++]);
}
cout << cnt << '\n';
for(int i = 0; i < cnt; i ++) {
sort(ctc[i].begin(), ctc[i].end());
for(auto j : ctc[i])
cout << j + 1 << ' ';
cout << '\n';
}
}