Pagini recente » Monitorul de evaluare | Cod sursa (job #395285) | Cod sursa (job #674675) | Cod sursa (job #2258208) | Cod sursa (job #1898732)
#include <bits/stdc++.h>
#define NMAX 1001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[NMAX], GT[NMAX], ctc[NMAX];
vector <bool> viz;
vector <int> postordine;
int nr, K;
void DFS(int nod) {
viz[nod] = true;
for(int i = 0; i < G[nod].size(); ++i) {
if(!viz[G[nod][i]]) {
DFS(G[nod][i]);
}
}
postordine[++nr] = nod;
}
void DFST(int nod) {
viz[nod] = false;
ctc[K].push_back(nod);
for(int i = 0; i < GT[nod].size(); ++i) {
if(viz[GT[nod][i]]) {
DFST(G[nod][i]);
}
}
}
int main() {
int N, M;
fin>>N>>M;
viz.resize(NMAX, false);
postordine.resize(NMAX, 0);
for(int x, y, i = 0; i < M; ++i) {
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i = 1; i <= N; ++i) {
if(!viz[i]) {
DFS(i);
}
}
for(int i = N; i > 0; --i) {
if(viz[postordine[i]]) {
K += 1;
DFST(postordine[i]);
}
}
fout<<K<<'\n';
for(int i = 1; i <= K; i++)
{
for(int j = 0; j < ctc[i].size(); j++)
fout << ctc[i][j] << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}