Pagini recente » Cod sursa (job #3153130) | Cod sursa (job #2814162) | Cod sursa (job #1106962) | Cod sursa (job #1154276) | Cod sursa (job #2159293)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 100005;
int N, M;
int Component;
vector <int> G[NMAX];
vector <int> R[NMAX];
vector < vector<int> > sol;
stack <int> t;
bool UseTopo[NMAX], Use[NMAX];
void Read(){
in >> N >> M;
for(int i = 1; i <= M; ++i){
int a, b;
in >> a >> b;
G[a].push_back(b);
R[b].push_back(a);
}
}
void DFSTopo(int node){
UseTopo[node] = true;
for(int i = 0; i < G[node].size(); ++i){
int neighbour = G[node][i];
if(!UseTopo[neighbour])
DFSTopo(neighbour);
}
t.push(node);
}
void DFSComponent(int node){
Use[node] = true;
sol[sol.size() - 1].push_back(node);
for(int i = 0; i < R[node].size(); ++i){
int neighbour = R[node][i];
if(!Use[neighbour])
DFSComponent(neighbour);
}
}
void Solve(){
for(int i = 1; i <= N; ++i)
if(!UseTopo[i])
DFSTopo(i);
while(!t.empty()){
int node = t.top();
t.pop();
if(!Use[node]){
vector <int> v;
sol.push_back(v);
DFSComponent(node);
}
}
}
void Print(){
out << sol.size() << "\n";
for(int i = 0; i < sol.size(); ++i){
for(int j = 0; j < sol[i].size(); ++j)
out << sol[i][j] << " ";
out << "\n";
}
}
int main(){
Read();
Solve();
Print();
return 0;
}