Pagini recente » Cod sursa (job #558751) | Cod sursa (job #2088446) | Profil StarGold2 | Cod sursa (job #2206795)
#include <iostream>
#include <fstream>
#include <vector>
#define DIM 100001
std::ifstream f("ctc.in");
std::ofstream g("ctc.out");
struct Node{
bool taken;
};
std::vector<int> G[DIM],sol[DIM],q;
Node node[DIM];
int n,m,k=0;
void read(){
f>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
f>>x>>y;
G[x].push_back(y);
}
f.close();
}
void init(){
for(int i=1;i<=n;i++){
node[i].taken= false;
}
}
void DFS_visit_p(int x){
node[x].taken=true;
for(int y:G[x]){
if(!node[y].taken){
DFS_visit_p(y);
q.push_back(y);
}
}
}
void DFS_p(){
init();
for(int i=1;i<=n;i++){
if(!node[i].taken) {
DFS_visit_p(i);
q.push_back(i);
}
}
}
void invert(){
std::vector<int> G1[DIM];
for(int i=1;i<=n;i++)
for(int j:G[i])
G1[j].push_back(i);
for(int i=1;i<=n;i++)
G[i]=G1[i];
}
void DFS_visit(int x){
node[x].taken=true;
sol[k].push_back(x);
for(int y:G[x]){
if(!node[y].taken){
DFS_visit(y);
}
}
}
void DFS(){
init();
while (!q.empty()){
int x=q.back();
q.pop_back();
if(!node[x].taken) {
DFS_visit(x);
k++;
}
}
}
void kosaraju(){
DFS_p();
invert();
DFS();
}
void print(){
g<<k<<"\n";
for(int i=0;i<k;i++){
for(int j:sol[i]){
g<<j<<" ";
}
g<<"\n";
}
g.close();
}
int main() {
read();
kosaraju();
print();
return 0;
}