Pagini recente » Cod sursa (job #1240917) | Cod sursa (job #2940238) | Cod sursa (job #1744412) | Cod sursa (job #2129455) | Cod sursa (job #1592117)
#include <fstream>
#include <vector>
#define NMAX 100010
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void DFS(int x);
void DFSt(int x);
int n, m, i, j;
vector <int> unu, doi[NMAX], M[NMAX*2], T[NMAX*2];
int elem, elem2, ctc, x, y;
vector <bool> v;
int main()
{
fin >> n >> m;
for(i = 1; i <= n; ++i)
v.push_back(false);
for(i = 1; i <= m; ++i)
{
fin >> x >> y;
M[x].push_back(y);
T[y].push_back(x);
}
for(i = 1; i <= n; ++i)
{
if(v[i] == false)
{
v[i] = true;
DFS(i);
//elem = 0;
}
}
for(i = unu.size()-1; i >= 0; --i)
{
if(v[unu[i]] == true)
{
v[unu[i]] = false;
ctc++;
DFSt(unu[i]);
}
}
fout << ctc << '\n';
for(i = 1; i <= ctc; ++i)
{
for(j = doi[i].size()-1; j >= 0; --j)
fout << doi[i][j] << ' ';
fout << '\n';
}
return 0;
}
void DFS(int x)
{
int i;
for(i = 0; i < M[x].size(); ++i)
{
if(v[M[x][i]] == false)
{
v[M[x][i]] = true;
DFS(M[x][i]);
}
}
unu.push_back(x);
}
void DFSt(int x)
{
int i;
for(i = 0; i < T[x].size(); ++i)
{
if(v[T[x][i]] == true)
{
v[T[x][i]] = false;
DFSt(T[x][i]);
}
}
doi[ctc].push_back(x);
}