Pagini recente » Cod sursa (job #2686799) | Cod sursa (job #3039145) | Cod sursa (job #1108223) | Cod sursa (job #2154196) | Cod sursa (job #1087488)
#include<fstream>
#include<vector>
#define Nmax 100010
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>G[Nmax], GT[Nmax], comp[Nmax];
vector<int>postord(Nmax+1);
int N, M, i, n, nrc;
bool viz[Nmax];
void DFSpostord(int nod)
{
int i, vecin;
viz[nod] = 1;
for (i = 0; i < G[nod].size(); ++i)
{
vecin = G[nod][i];
if (!viz[vecin])
DFSpostord(vecin);
}
postord[++n] = nod;
}
void DFS(int nod)
{
int i, vecin;
viz[nod] = 0; comp[nrc].push_back(nod);
for (i = 0; i < GT[nod].size(); ++i)
{
vecin = GT[nod][i];
if (viz[vecin])
DFS(vecin);
}
}
int main()
{
int x, y;
fin >> N >> M;
for (i = 1; i <= M; ++i)
{
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for (i = 1; i <= N;++i)
if (!viz[i])
DFSpostord(i);
for (i = N; i >= 1;--i)
if (viz[postord[i]])
{
nrc++;
DFS(postord[i]);
}
fout << nrc << '\n';
for (i = 1; i <= nrc; ++i)
{
for (int j = 0; j<comp[i].size();++j)
fout << comp[i][j] << ' ';
fout << '\n';
}
return 0;
}