Pagini recente » Cod sursa (job #1769801) | Cod sursa (job #2740647) | Cod sursa (job #2025275) | Cod sursa (job #1170762) | Cod sursa (job #2087097)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 100005;
vector <int> G[NMAX];
vector <int> Ginv[NMAX];
vector <int> sol[NMAX];
int N, M;
int conexe;
int comp[NMAX];
int pred[NMAX], succ[NMAX];
void Read(){
in >> N >> M;
for(int i = 1; i <= M; ++i){
int a, b;
in >> a >> b;
G[a].push_back(b);
Ginv[b].push_back(a);
}
}
void Forw(int node){
succ[node] = conexe;
for(int i = 0; i < G[node].size(); ++i){
int neighbour = G[node][i];
if(!succ[neighbour])
Forw(neighbour);
}
}
void Backw(int node){
pred[node] = conexe;
for(int i = 0; i < Ginv[node].size(); ++i){
int neighbour = Ginv[node][i];
if(!pred[neighbour])
Backw(neighbour);
}
}
void Merge(){
for(int i = 1; i <= N; ++i){
if(pred[i] == succ[i] && pred[i] == conexe)
sol[conexe].push_back(i);
else if(pred[i] != succ[i])
pred[i] = succ[i] = 0;
}
}
void Solve(){
for(int i = 1; i <= N; ++i){
if(!succ[i]){
conexe++;
Forw(i);
Backw(i);
Merge();
}
}
}
void Print(){
out << conexe << "\n";
for(int i = 1; i <= conexe; ++i){
for(int j = 0; j < sol[i].size(); ++j)
out << sol[i][j] << " ";
out << "\n";
}
}
int main(){
Read();
Solve();
Print();
}