Pagini recente » Cod sursa (job #846474) | Cod sursa (job #1346300) | Cod sursa (job #1070813) | Cod sursa (job #1471068) | Cod sursa (job #2071841)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream in("date.in");
ifstream in("ctc.in");
//ofstream out("date.out");
ofstream out("ctc.out");
const int NMax = 1e5;
int N, M, NrConexe;
vector <int> G1[NMax], G2[NMax];
int UseP[NMax], UseN[NMax];
void Read(){
in >> N >> M;
int x, y;
while (M--){
in >> x >> y;
G1[x].push_back(y);
G2[y].push_back(x);
}
}
void DFS1(int Nod){
UseN[Nod] = NrConexe;
for (int i = 0; i < (int)G1[Nod].size(); ++i){
int Vecin = G1[Nod][i];
if (!UseN[Vecin])
DFS1(Vecin);
}
}
void DFS2(int Nod){
UseP[Nod] = NrConexe;
for (int i = 0; i <(int)G2[Nod].size(); ++i){
int Vecin = G2[Nod][i];
if (!UseP[Vecin])
DFS2(Vecin);
}
}
void Solve(){
for (int i = 1; i <= N; ++i)
if (!UseN[i]){
NrConexe ++;
DFS1(i);
DFS2(i);
for (int j = 1; j <= N; ++j)
if (UseN[j] != UseP[j])
UseN[j] = UseP[j] = 0;
}
}
void Print(){
out << NrConexe << '\n';
for (int i = 1; i <= NrConexe; out << '\n', ++i)
for (int j = 1; j <= N; ++j)
if (UseN[j] == i)
out << j << " ";
}
int main()
{
Read();
Solve();
Print();
return 0;
}