Pagini recente » Cod sursa (job #3353004) | Cod sursa (job #3306959) | Cod sursa (job #3322549) | Cod sursa (job #3352683) | Cod sursa (job #3340298)
#include <fstream>
#include <vector>
using namespace std;
int n;
vector<vector<int>> G, GT;
vector<bool> apar;
vector<int> term;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void read(){
int m;
fin >> n >> m;
G = GT = vector<vector<int>> (n + 1);
for(int i = 1; i <= m; i++){
int x, y;
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void reset(){
apar = vector<bool> (n + 1, 0);
}
void dfs(int nod){
apar[nod] = 1;
for(auto x: G[nod])
if(!apar[x])
dfs(x);
term.push_back(nod);
}
vector<int> empty_vector;
vector<vector<int>> components;
void dfsT(int nod){
apar[nod] = 1;
for(auto x: GT[nod])
if(!apar[x])
dfsT(x);
components.back().push_back(nod);
}
int main(){
read();
reset();
for(int i = 1; i <= n; i++)
if(!apar[i])
dfs(i);
reset();
for(int i = term.size() - 1; i >= 0; i--)
if(!apar[term[i]]){
components.push_back(empty_vector);
dfsT(term[i]);
}
fout << components.size() << '\n';
for(vector<int> &c: components){
for(int node: c) fout << node << ' ';
fout << '\n';
}
}