Pagini recente » Rating Elisabeta-Ioana Mercas (elisaioanamercas) | Cod sursa (job #2092716) | Cod sursa (job #1882708) | Cod sursa (job #1352309) | Cod sursa (job #1491062)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int Maxn = 100005;
int n, m, nr_el;
vector <int> G1[Maxn], G2[Maxn], G[Maxn], pos, q, u;
void Read();
void DFP(int x);
void DFM( int x, int which);
void Print();
int main(void)
{
Read();
u.resize(n);
u.assign(u.size(), 0);
for (int i = 0; i < n; ++ i) if (u[i] == false)
DFP(i);
pos.resize(n);
pos.assign(pos.size(), -1);
while(q.size())
{
if (pos[q.back()] == -1)
{
DFM(q.back(), nr_el);
nr_el ++;
}
q.pop_back();
}
for (int i = 0; i < n; ++ i)
G[pos[i]].push_back(i);
Print();
return 0;
}
void Read()
{
int x, y;
fin >> n;
fin >> m;
for (int i = 1; i <= m; i++)
{
fin >> x >> y;
x --, y --;
G1[x].push_back(y);
G2[y].push_back(x);
}
}
void Print()
{
fout << nr_el << '\n';
for (int i = 0; i < nr_el; ++ i)
{
for (auto it : G[i])
fout << it + 1 << " ";
fout << '\n';
}
fout.close();
}
void DFP(int x)
{
u[x] = true;
for (auto it : G1[x] )
if (u[it] == false)
DFP(it);
q.push_back(x);
}
void DFM( int x, int which)
{
pos[x] = which;
for (auto it : G2[x])
if (pos[it] == -1)
DFM(it, which);
}