Pagini recente » Cod sursa (job #115563) | Cod sursa (job #2258403) | Cod sursa (job #2238912) | Cod sursa (job #2156929) | Cod sursa (job #1898733)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[NMAX], GT[NMAX], CtC[NMAX], P;
vector <bool> viz;
int k, nr;
void DFS(int nod)
{
viz[nod] = 1;
for(int i = 0; i < G[nod].size(); i++)
if(!viz[G[nod][i]])
DFS(G[nod][i]);
P[++k] = nod;
}
void DFST(int nod)
{
viz[nod] = 0;
CtC[nr].push_back(nod);
for(int i = 0; i < GT[nod].size(); i++)
if(viz[GT[nod][i]])
DFST(GT[nod][i]);
}
int main()
{
int N, M;
fin >> N >> M;
for(int x, y, i = 1; i <= M; ++i)
{
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
viz.resize(NMAX, false);
P.resize(NMAX);
for(int i = 1; i <= N; i++)
if(!viz[i])
DFS(i);
for(int i = N; i > 0; i--)
if(viz[P[i]])
{
nr++;
DFST(P[i]);
}
fout << nr << '\n';
for(int i = 1; i <= nr; i++)
{
for(int j = 0; j < CtC[i].size(); j++)
fout << CtC[i][j] << ' ';
fout << '\n';
}
return 0;
}