Pagini recente » Cod sursa (job #1902320) | Cod sursa (job #2567373) | Cod sursa (job #3134201) | Cod sursa (job #2873999) | Cod sursa (job #3226206)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <bitset>
#include <algorithm>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100000;
vector< vector<int> >succ;
vector< vector<int> >pred;
vector< vector<int> >ctc;
vector<int>sort_top;
bitset<N + 1> viz;
void dfs(int x){
viz[x] = 1;
for(auto y : succ[x]){
if(!viz[y]){
dfs(y);
}
}
sort_top.push_back(x);
}
void dfst(int x, vector<int>&v){
viz[x] = 1;
v.push_back(x);
for(int i : pred[x]){
if(!viz[i]){
dfst(i, v);
}
}
}
int main(){
int n, m;
in >> n >> m;
succ.resize(n + 1);
pred.resize(n + 1);
for(int i = 1; i <= m; i++){
int x, y;
in >> x >> y;
succ[x].push_back(y);
pred[y].push_back(x);
}
viz.reset();
for(int i = 1; i <= n; i++){
if(!viz[i]){
dfs(i);
}
}
reverse(sort_top.begin(), sort_top.end());
viz.reset();
for(int i : sort_top){
if(!viz[i]){
vector<int>v;
dfst(i, v);
ctc.push_back(v);
}
}
out << ctc.size() << '\n';
for(auto i : ctc){
for(auto j : i){
out << j << " ";
}
out << '\n';
}
in.close();
out.close();
return 0;
}