Pagini recente » Cod sursa (job #965452) | Cod sursa (job #127378) | Cod sursa (job #46988) | Cod sursa (job #2588807) | Cod sursa (job #1424523)
#include <fstream>
#include <vector>
#define Max_N 100010
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int N, M, POST_OR[Max_N];
vector < int > VU[Max_N], VD[Max_N];
vector < vector < int > > Sol;
bool viz[Max_N];
void Read_Data();
void DFS_1(int );
void DFS_2(int );
void Solve();
void Write_Data();
int main()
{
Read_Data();
Solve();
Write_Data();
return 0;
}
void Read_Data()
{
fin >> N >> M;
for (int i = 1, x, y; i <= M; i++)
{
fin >> x >> y;
VU[x].push_back(y);
VD[y].push_back(x);
}
}
void DFS_1(int nod)
{
viz[nod] = 1;
for (vector < int > :: iterator it = VU[nod].begin(); it != VU[nod].end(); it++) {
if (!viz[*it]) {
DFS_1(*it);
}
}
POST_OR[++POST_OR[0]] = nod;
}
void DFS_2(int nod)
{
viz[nod] = 0;
Sol[Sol.size() - 1].push_back(nod);
for (vector < int > :: iterator it = VD[nod].begin(); it != VD[nod].end(); it++) {
if (viz[*it]) {
DFS_2(*it);
}
}
}
void Solve()
{
for (int i = 1; i <= N; i++) {
if (!viz[i]) {
DFS_1(i);
}
}
for (int i = N; i >= 1; i--) {
if (viz[POST_OR[i]]) {
Sol.push_back(vector < int > (0));
DFS_2(POST_OR[i]);
}
}
}
void Write_Data()
{
fout << Sol.size() << '\n';
for (int i = 0; i < Sol.size(); i++) {
for (int j = 0; j < Sol[i].size(); j++) {
fout << Sol[i][j] << ' ';
}
fout << '\n';
}
fout.close();
}