Pagini recente » Cod sursa (job #25744) | Cod sursa (job #618943) | Cod sursa (job #207589) | Cod sursa (job #1257) | Cod sursa (job #1097707)
//
// main.cpp
// Componente tare conexe
//
// Created by Stefan Iarca on 2/3/14.
// Copyright (c) 2014 Stefan Iarca. All rights reserved.
//
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 100010
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[NMAX], Gt[NMAX],Cicluri[NMAX];
bool Used[NMAX];
int N,M,O[NMAX],k,Count;
void Read(){
f>>N>>M; int x,y;
for (int i = 1; i <= M; i++) {
f>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void DFS(int Node){
Used[Node] = true;
for (vector<int>::iterator it = G[Node].begin(); it < G[Node].end(); it++) {
if (!Used[*it]) {
DFS(*it);
}
}
O[++k] = Node;
}
void DFSt(int Node){
Used[Node] = true;
Cicluri[Count].push_back(Node);
for (vector<int>::iterator it = Gt[Node].begin(); it < Gt[Node].end(); it++) {
if (!Used[*it]) {
DFSt(*it);
}
}
}
void Solve(){
for (int i = 1; i <= N; i++) {
if(!Used[i]){
DFS(i);
}
}
for (int i = 0; i <= N; i++) {
Used[i] = false;
}
for (int i = k; i > 0 ; i--) {
if(!Used[O[i]]){
Count++;
DFSt(O[i]);
}
}
}
void Write(){
g<<Count<<"\n";
for (int i = 1; i <= Count; i++) {
for (vector<int>::iterator it = Cicluri[i].begin(); it < Cicluri[i].end(); it++) {
g<<*it<<" ";
}
g<<"\n";
}
}
int main()
{
Read();
Solve();
Write();
return 0;
}