Pagini recente » Cod sursa (job #3239714) | Cod sursa (job #712473) | Cod sursa (job #3032794) | Cod sursa (job #847684) | Cod sursa (job #3271063)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N,M,i,j,a,b,ctc_cur;
vector<int> G[100005],rG[100005];
int ctc[100005];
deque<int> s;
bool v[100005];
vector<int> ans[100005];
void dfs(int k){
v[k] = 1;
for (auto next_k : G[k])
if (!v[next_k])
dfs(next_k);
s.push_front(k);
}
void kosaraju(int k){
ctc[k] = ctc_cur;
ans[ctc_cur].push_back(k);
for (auto next_k : rG[k])
if (!ctc[next_k])
kosaraju(next_k);
}
int main()
{
fin >> N >> M;
for (i = 1;i <= M;i++){
fin >> a >> b;
G[a].push_back(b);
rG[b].push_back(a);
}
for (i = 1;i <= N;i++)
if (!v[i])
dfs(i);
for (auto k : s)
if (!ctc[k]){
ctc_cur++;
kosaraju(k);
}
fout << ctc_cur << "\n";
for (i = 1;i <= 100000;i++)
if (ans[i].size() == 0)
break;
else{
for (auto node : ans[i])
fout << node << " ";
fout << "\n";
}
return 0;
}